马步距离（经典BFS）

admin

在一个n*n的棋盘上有个马在x y处，跳到xx，yy处至少需要几步？
这个题是典型的广搜BFS的例子，当然也可以用深搜来做，枚举所有的的从x y点到xx yy点的路径，找到其中最短的哪一条，但是这里，我们用广搜来解决这个题，学习一种新的搜索方法。
马在xy处，第一步可以跳到(x+1，y+2)或者(x+2,y+1)或者(x+2,y-1)等8处，只要这个点没有越出棋盘范围都可以，按顺序保存下这些点，要是到达了终点，那就算是找到了，没有的话，先选取第一个点(x+1,y+2)，再看看他能跳到哪8个地方，按顺序把这些点加入到刚才的序列，判断是否目标终点，不是的话就一次选择后面的(x+1,y+2)进行扩展，继续如此做，直到到达终点或者证明找不到。假设起点是1,1，终点是4,4。我们来模拟这个过程。

1. ///n*n的棋盘上马在x y处，跳到xx yy处至少需要几步？
   
2. #include <iostream>
   
3. #include <iomanip>
   
4. using namespace std;
   
5. const int mm=100010;/// 最多的状态数目
   
6. const int mn=13; ///棋盘最大12*12
   
7. struct horse
   
8. {
   
9.         int x,y,f;
   
10. } a[mm],temp;
    
11. int m[mn][mn];///记录到达此点的最少步数，兼判断重复
    
12. int n,x,y,xx,yy;
    
13. int h,t;
    
14. int dx[]= {0,+1,+2,+2,+1,-1,-2,-2,-1};
    
15. int dy[]= {0,+2,+1,-1,-2,+2,+1,-1,-2};
    
16. bool can(int x,int y)  ///xy点是否能到达
    
17. {
    
18.         if (x<1 || x>n || y<1 || y>n) return 0;///越界
    
19.         if (m[x][y]>-1) return 0;/// 已经经历
    
20.         return 1;
    
21. }
    
22. void check()
    
23. {
    
24.         int i,j;
    
25.         for (i=1; i<=n; i++)
    
26.                 {
    
27.                         for (j=1; j<=n; j++) cout<<setw(2)<<m[i][j];
    
28.                         cout<<endl;
    
29.                 }
    
30.         for (i=1; i<=40; i++) cout<<a[i].x<<' ';
    
31.         cout<<endl;
    
32.         for (i=1; i<=40; i++) cout<<a[i].y<<' ';
    
33.         cout<<endl;
    
34.         for (i=1; i<=40; i++) cout<<a[i].f<<' ';
    
35.         cout<<endl;
    
36. 
    
37. }
    
38. void pp()
    
39. {
    
40.         int i=1,j;
    
41.         int p[50];///最多50步，表示路径
    
42.         p[1]=j=h;
    
43.         while (a[j].f!=0)        p[++i]=j=a[j].f;  ///非常精妙的写法
    
44.         for (; i>=1; i--)cout<<a[p[i]].x<<' '<<a[p[i]].y<<"->";
    
45.         cout<<xx<<' '<<yy;
    
46. }
    
47. int main()
    
48. {
    
49.         n=8,x=1,y=1,xx=1,yy=2; ///初始
    
50.         for (int i=1; i<=n; i++)
    
51.                 for (int j=1; j<=n; j++) m[i][j]=-1;
    
52.         m[1][1]=0;
    
53. 
    
54.         bool b=1;
    
55.         h=1,t=2;
    
56.         a[h].x=1,a[h].y=1,a[h].f=0;
    
57.         while (t<=mm-100 && h<t && b)
    
58.                 {
    
59.                         temp=a[h];
    
60.                         for (int r=1; r<=8; r++) /// 8个规则
    
61.                                 {
    
62.                                         int tx=temp.x+dx[r],ty=temp.y+dy[r];
    
63.                                         cout<<tx<<' '<<ty<<endl;
    
64.                                         if (tx==xx&& ty==yy)  ///是目标节点
    
65.                                                 {
    
66.                                                         b=0;
    
67.                                                         break;
    
68.                                                 }
    
69.                                         if (can(tx,ty))  ///符合条件加入队列
    
70.                                                 {
    
71.                                                         m[tx][ty]=m[temp.x][temp.y]+1; ///判断重复
    
72.                                                         a[t].x=tx,a[t].y=ty,a[t].f=h;
    
73.                                                         t++;
    
74.                                                 }
    
75.                                 }
    
76.                         if(b==1)h++; ///未找到继续找，找到了就算了
    
77.                 }
    
78.         check();
    
79.         if (t>mm-100) cout<<"i cannot find!";
    
80.         else if (h>t) cout<<"cannot find!";
    
81.         else if (b==0) pp();
    
82.         return 0;
    
83. }

复制代码

admin

算法是基本框架是：
初始化棋盘和马的位置
初始化队列，马的位置进入队列
while （队列里面有元素  || 还有空间继续寻找 || 还没有找到）
{  取出队头元素temp
    for （规则=1 to n）
       {
             新的状态=temp按规则生的儿子
            if （生的儿子合法  没有被经过 没有越界）
            {
                if （是终点） 搜索结束，转到打印输出路径子程序
               else 进入队列
            }
       }
}

admin

我们现在一步步的完成上面的步骤，复习一下以前说的步步为营的做法，
马每一步的状态我们用记录类型三元组x,y,f表示，分别表示马当前的位置和他的爸爸（上一位置便于回溯找到完整的路径），也可以加上一个c表示到此步的步数或者d表示到此步的规则，视题目要求而定，有时当不需要路径的时候连f也可以不记录。
所有的马的状态的总和我们称为综合数据库，满足典型的先进先出FIFO，其实是一个队列，可以用c++中自带的queue或者是数组模拟queue，有的时候要输出完整的路径，用queue就不方便了，因为没有保存中间的结果，这里我们选用数组模拟法，a[mm]数组存放所有的可能情况，head和tail作为指针变量存放当前的队列头和尾。
马的8种跳法用增量偏移数组，dxdy表示，这个在金币2467那个题中已经详细讲过。
跳马的约束条件是跳过的地方不能再跳到，不能超出棋盘范围，这个可以用类似8皇后的can函数计算。

admin

这是广搜（BFS）一个很经典的简单例子，里面涉及几个问题，我们一起分解：
1、状态如何表示
2、规则如何表示
3、

和深搜（DFS）有点不同，
1、一般的BFS都是队列实现，不用递归或者栈
2、一般有判重代码段
3、一般有找爸爸回溯路径的代码段