马跳棋盘问题

admin

经典问题：5*5的象棋棋盘上左下角有一个马，它能否从这点出发，把剩下的24个点都不重复的跳一次？

admin

完整程序：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int dx[]= {0,+1,+2,+2,+1,-1,-2,-2,-1};
   
4. int dy[]= {0,+2,+1,-1,-2,+2,+1,-1,-2};
   
5. const int mn=10;
   
6. int x[mn],y[mn],m[mn][mn];
   
7. int  n;
   
8. bool can(int x,int y)  ///xy点是否能到达
   
9. {
   
10.         if (x<1 || x>n || y<1 || y>n) return 0;///越界
    
11.         if (m[x][y]>0) return 0;/// 已经被用
    
12.         return 1;
    
13. }
    
14. 
    
15. void pr()
    
16. {
    
17.         for (int y=n; y>=1; y--)
    
18.                 {
    
19.                         for (int x=1; x<=n; x++) cout<<setw(3)<<m[y][x];
    
20.                         cout<<endl;
    
21.                 }
    
22. }
    
23. void dfs(int i)
    
24. {
    
25.         if (i>n*n) pr();
    
26.         else for(int k=1; k<=8; k++)
    
27.                         {
    
28.                                 ///预判下一个点
    
29.                                 int tx=x[i-1]+dx[k];
    
30.                                 int ty=y[i-1]+dy[k];
    
31.                                 if (can(tx,ty))
    
32.                                         {
    
33.                                                 x[i]=tx,y[i]=ty;
    
34.                                                 m[tx][ty]=i;
    
35.                                                 dfs(i+1);
    
36.                                                 m[tx][ty]=0;
    
37.                                         }
    
38.                         }
    
39. }
    
40. 
    
41. int main()
    
42. {
    
43.         n=5;
    
44.         ///标志数组清0
    
45.         for (int x=1; x<=5; x++)
    
46.                 for (int y=1; y<=5; y++) a[x][y]=0;
    
47.         x[1]=y[1]=1;/// 1,1处起步
    
48.         m[1][1]=1; ///第一个标记
    
49.         dfs(2);
    
50.         return 0;
    
51. }

复制代码

admin

主函数 dfs就和标准的pmn没什么区别，上面分析的各个函数对号入座。

1. void dfs(int i)
   
2. {
   
3.         if (i>n*n) pr();
   
4.         else for(int k=1; k<=8; k++)
   
5.                         {
   
6.                                 ///预判下一个点
   
7.                                 int tx=x[i-1]+dx[k];
   
8.                                 int ty=y[i-1]+dy[k];
   
9.                                 if (can(tx,ty))
   
10.                                         {
    
11.                                                 x[i]=tx,y[i]=ty;
    
12.                                                 m[tx][ty]=i;
    
13.                                                 dfs(i+1);
    
14.                                                 m[tx][ty]=0;
    
15.                                         }
    
16.                         }
    
17. }
    

复制代码

admin

现在又来讲基本功了，前面我们假设的棋盘在第一象限，那么输出棋盘的时候应该外层循环是y，内层循环是x，（先行后列吗！）
而且，y还应该是递减行的，这个我们在前面数字图案的时候讲过，不要忘记了。

1. void pr()
   
2. {
   
3.         for (int y=n; y>=1; y--)
   
4.                 {
   
5.                         for (int x=1; x<=n; x++) cout<<setw(3)<<m[y][x];
   
6.                         cout<<endl;
   
7.                 }
   
8. }

复制代码

假设当前点是  x y，那么下一个点最多有8 个可能，这8 个可能可以类似扫雷那样用方向数组来表示，免得写8条单独的语句，方向数组按我们的惯例叫做dx dy，首地址0不要了。这是一种很常用的技巧，大家要注意。

1. int dx[]= {0,+1,+2,+2,+1,-1,-2,-2,-1};
   
2. int dy[]= {0,+2,+1,-1,-2,+2,+1,-1,-2};
   
3. 
   
4. for(int k=1; k<=8; k++)
   
5.         ///预判下一个点
   
6.         int tx=x[i-1]+dx[k];
   
7.         int ty=y[i-1]+dy[k];

复制代码

和pmn一样，以前选过的现在不能选，以前到达过的点现在不能再去，还有一个限制类似间隔排列，超过边界的点不能到达，这两个可以合二为一叫can(x,y)函数，他用于判断能否有效到达(x,y)点。体会下8皇后的第一种做法我也用了这样原始的判断方法。

1. bool can(int x,int y)  ///xy点是否能到达
   
2. {
   
3.         if (x<1 || x>n || y<1 || y>n) return 0;///越界
   
4.         if (m[x][y]>0) return 0;/// 已经被用
   
5.         return 1;
   
6. }

复制代码

admin

再细化这个程序，我们用 a[8][8]表示棋盘，这次我们假设棋盘在直角坐标系第一象限，(1,1)是左下角， (5,5)是右上角，那么a[x][y]的值就是表示第几步到达此点，这个也同时兼pmn中的标志位数组B的作用，=0表示未曾到达以后可以到达，>0表示已经经过以后不能再到达。
比如下面这个方案，表示起始位置（第一步）在1,1，第二步到达3,2，第三步到达5,3，第四步到达4,5******。对应输出棋盘应该是这样的，也很直观

admin

在做这个题之前，我们要复习一下以前做过的几个题目，因为里面的有些知识和技巧，这里需要用到。
1、扫雷，注意体会方向数组的使用；http://hsyit.cn/forum.php?mod=viewthread&tid=35817
2、奇数阶幻方，注意二维数组输出，体会tr，tc这种预算下一个，可行的话再填入的过程；http://hsyit.cn/forum.php?mod=viewthread&tid=36112
3、pmn，体会其中m种可能，可以的话就选择，然后标记，记录，再选下一个的过程。 http://hsyit.cn/forum.php?mod=viewthread&tid=69311

那么这个跳马问题大框架可以仿照pmn，就是这么做：第一个位置是(1，1)，从第二个位置开始搜索，
若已经到了第26个位置，说明已经经过了25个点，每个位置都到了，输出结果
  否则  对于马有8条规则
       如果下一个位置是满足条件的   
         到达此位置，
         此位置标记下次不能来了
         搜索下一个
         重新标记此位置可以到

admin

很好的综合应用题，大家要好好体会，用来检查前期的只是掌握情况，

admin

有点思维难度的DFS，
从x=1 y=1开始跳完需要24步。
每一步有8个可能，当然越界的不算，和8皇后有点类似
最后一步跳完程序就可以结束了