华师一附中OI组

标题: 马跳棋盘问题 [打印本页]
作者: admin    时间: 2020-4-11 18:16
标题: 马跳棋盘问题
经典问题：5*5的象棋棋盘上左下角有一个马，它能否从这点出发，把剩下的24个点都不重复的跳一次？
作者: admin    时间: 2020-4-11 18:18
有点思维难度的DFS，
从x=1 y=1开始跳完需要24步。
每一步有8个可能，当然越界的不算，和8皇后有点类似
最后一步跳完程序就可以结束了
作者: admin    时间: 2020-4-11 18:23
很好的综合应用题，大家要好好体会，用来检查前期的只是掌握情况，
作者: admin    时间: 2020-4-23 10:57
在做这个题之前，我们要复习一下以前做过的几个题目，因为里面的有些知识和技巧，这里需要用到。
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    时间: 2020-4-23 11:11
再细化这个程序，我们用 a[8][8]表示棋盘，这次我们假设棋盘在直角坐标系第一象限，(1,1)是左下角， (5,5)是右上角，那么a[x][y]的值就是表示第几步到达此点，这个也同时兼pmn中的标志位数组B的作用，=0表示未曾到达以后可以到达，>0表示已经经过以后不能再到达。
比如下面这个方案，表示起始位置（第一步）在1,1，第二步到达3,2，第三步到达5,3，第四步到达4,5******。对应输出棋盘应该是这样的，也很直观

作者: admin    时间: 2020-4-26 13:17
现在又来讲基本功了，前面我们假设的棋盘在第一象限，那么输出棋盘的时候应该外层循环是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};

  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    时间: 2020-4-26 13:28
主函数 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    时间: 2020-4-26 13:30
完整程序：
  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. }

  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. }

  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2