四子连棋

这是我到目前为止写过最长的代码之一……


题意

44的棋盘,一共有三种属性:白棋,黑棋,空格(有且仅有两个),每一次可以移动一颗棋子,*黑白棋交替进行,只能移到空格的地方。求达成四子连棋局面(横竖斜都算**)所需的最小步数

分析

  • 广搜,和八数码问题差不多,但是更繁琐了。
  • 黑白棋交替进行,那么我们需要在搜索的时候除了当前地图和步数还需要保存当前该哪一方行棋
  • 广搜要搜两遍,分别是黑棋先走或白棋先走
  • 每一次需要考虑两个空格,所以从两个当前点搜状态

遇到的坑

  • 很多都是重复的代码,只要细心就好了,但有一个最坑的……

  • 黑棋先走和白棋先走走到的棋局相同的情况也是两种情况,不能判重删去!!!

汉诺塔问题

题面

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

自己汉诺塔问题晕了很久,但搜索写多了至少也有一些通悟

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×