Question

C++编写骑士巡游问题

在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 — 问题无解）。提示：（1）“棋盘”可用二维数组B表示。（2）编制一个具有如下原型的递归函数solve，用于完成任务：从(i,j)点出发，做第k至第n*n（即n的平方）次的移动 — 将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中，若成功则通过引用参数ok返回true，否则返回false。void solve(int i, int j, int k, bool& ok)；（3）编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”（数码）1，而后进行调用“solve(x1, y1, 2, ok);”来完成所求任务。

Answer 1

这里还需要一个函数，就是规则函数，即你的骑士当前坐标能走的点有哪些，这个比较麻烦，我就大致说明下了class point{ public: int x; int y; point(){x=0;y=0;} point(x1,y1){x=x1;y=y1;} ~point(){}}; //下面是规则函数，我就大概写下，pointList没声明啊，可以自己写。就是point类的一个列表pointList rule(int x,int y){....} //返回当前x和y坐标下可以走的点int B[n][n]; //n是已知的啊，自己define去 这个是全局的 void solve(int i,int j int k, bool & ok){ if（B[i][j]!=0） { ok=false; return; //B数组一开始都初始化成0,main里面会做，如果不为0,表示已经走过改点，递归结束 } pointList list=rule(i,j);//先获取可以走的点集合 if(list.cout()==0) { //如果发现没有可走的点了，检查是否每个点都走过了，看B数组是否都是非0值 bool result=true; for(int p=0;p<n;p++) for(int q=0q<n;q++) { if(B[p][q]==0) { result=false; break; } } if(result) //如果都走完了，证明可以了 { ok=true; return; } } else { //递归调用 B[i][j]=k; //先记录走的顺序， for(int m=0;m<list.count();m++) //递归 { int x1=list[m].x; int y1=list[m].y; solve(x1,y1,++k,ok); //记得k值+1; if(!ok) B[x1][y1]=0; //这步是递归的精华，如果递归失败，一定要让数组变0，表示回滚操作，否则递归就没意义了。 if(ok) return; } }} } void main(){ int x,y; for(int i=0;i<n;i++) for(int j=0;j<n;j++) B[i][j]=0; //初始化数组 cin>>x; cout<<endl; cin>>y; bool ok; solve(x,y,1,ok);//传引用ok if(ok) //可以 { //自己添加可行性操作 } else { //添加不可行的操作 }}