主要内容 #
- 问题描述
- 计算方法
- 参考代码
1. 问题描述 #
在5*5格的棋盘上,有一只象棋的马,从(1,1)点出发,按日字跳马,它可以朝8个方向跳,但不允许出界或跳到已跳过的格子上,要求在跳遍整个棋盘。
输出前5个方案及总方案数。
输出格式示例:
1 16 21 10 25
20 11 24 15 22
17 2 19 6 9
12 7 4 23 14
3 18 13 8 5
2. 计算方法 #
我们在寻找解决方案,当遇到有多种选择方案时,我们先选择一个方案进行尝试,如果走不通,则返回选择另外的方案进行尝试。
对应到我们的游戏中,则:如下图,我们所处现在的位置有8种格子可走,我们可以先选择编号为0的格子尝试走下去,如果无法通关,我们可以重新返回到当前位置,尝试走编号为1的格式,仍然不行再返回选择2…
3. 参考代码 #
#include <iostream> using namespace std; int u[8]={1,2,2,1,-1,-2,-2,-1}, //8个方向上的x,y增量 v[8]={-2,-1,1,2,2,1,-1,-2}; int a[100][100]={0},num=0; //记每一步走在棋盘的哪一格和棋盘的每一格有 //没有被走过, num表示方案总数 bool b[100][100]={0}; //表示方格是否被走过 int search(int,int,int); //以每一格为阶段,在每一阶段中试遍8个方向 int print(); //打印方案 int main() { a[1][1]=1;b[1][1]=1; //从(1,1)第一步开始走 search(1,1,2); //从(1,1)开始搜第2步该怎样走 cout<<num<<endl; //输出总方案(304) } int search(int i,int j,int n) { int k,x,y; //这三个变量一定要定义局部变量 if (n>25) { print(); return 0;} //走完了所有的25个方格、打印结果,统计方案 for (k=0;k<=7;k++) //试遍8个方向 { x=i+u[k];y=j+v[k]; //走此方向,得到的新坐标 if (x<=5&&x>=1&&y<=5&&y>=1&&(!b[x][y])) { //如果新坐标在棋盘上,并且这一格可以走 b[x][y]=1; a[x][y]=n; search(x,y,n+1); //从(x,y)去搜下一步该如何走 b[x][y]=0; a[x][y]=0; } } } int print() { num++; //统计总方案 if (num<=5) //打印出前5种方案 { for (int k=1;k<=5;k++) //打印本次方案 { for (int kk=1;kk<=5;kk++) cout<<" "<<a[k][kk]; cout<<endl; } cout << endl; } }