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

题意

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

分析

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

遇到的坑

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

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

题面

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

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

不妨假设：

• 当只有

  1

  1个盘子

  时

  1. 把盘子从A直接移到C

• 当只有

  1

  2个盘子

  时

  1. 将上面的盘子从A移动到B
  2. 将下面的盘子从A移动到C
  3. 将B上的盘子从B移动到C

• 当有

  1

  3个盘子

  时

  1. 将上面的盘子从A移动到C
  2. 将中间的盘子从A移动到B
  3. 将C上的盘子从C移动到B
  4. 将下面的盘子从A移动到C
  5. 将B上面的盘子从B移到A
  6. 将B上的盘子从B移到C
  7. 将A上的盘子从A移到C

可以发现当有3个盘子时，中间就会转化成2个盘子的情况，2个盘子最后就会转化成1个盘子的情况，显然可采用递归的方法

思路

把n-1个盘子移到B，再把最下面的盘子移到C，再把B上的n-1个盘子移到C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <cstdio>
using namespace std;

int ans,n;

void dfs(int x,int a,int b,int c)// num from  trans   end
{
    if(x==1)
    {
        printf("move from %d to %d\n",a,c);
        ans++;
     	return;   
    }
    dfs(x-1,a,c,b);
    printf("move from %d to %d\n",a,c);
    ans++;
    dfs(x-1,b,a,c);
}

int main()
{
    scanf("%d",&n);
    dfs(n,1,2,3);
    printf("need %d steps\n",ans);
	return 0;
}

自己遇到的坑

• a,b,c三个柱子没有搞清楚，递归函数里到底四个参数分别代表什么要搞清楚

其他一些……

• f[n]=f[n-1]*2+1

  本次的次数就等于把n-1个盘子移动了两回，加上剩下的最大的盘子移动的一次