Question

编程题``用c++编``明天就用急``运行成功的追加分

编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 — 问题无解）。
当n=5时，意味着要在5行5列的棋盘的25个“点”处，按骑士行走规则，依次将1至25这25个“棋子”（数码）分别摆放到棋盘上（摆满25个位置则成功，否则失败问题无解）。
例如，当n=5且初始坐标位置定为(1，1) — 即最左上角的那个点时，如下是一种巡游“路线图”。程序执行后的输出结果为：
(x1,y1)? => (1=>5, 1=>5) : 1 1
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
提示：
（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);”来完成所求任务。
欲处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。
可分解化简为如下两个子问题（正是形成递归函数的基础）：
① 由点(x1,y1)出发，按所给行走规则作1次移动到达(g,h)（或发现无路可走）；
② 从(g,h)点出发，按所给行走规则，作23次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。
solve函数具体实现时，若由(i,j)点出发已“无路可走”，则将引用参数ok置为false而递归出口；否则，先“迈一步”到达(g,h)点，而后再进行递归调用：solve(g, h, k+1, ok)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则通过引用参数ok返回true（否则返回false）。
点评：
（1）也可编制第二种解法的主函数：将棋盘上的n平方个点依次作为巡游起点的初始坐标位置(x1,y1)，判断从每一位置出发是否有解或无解（输出“OK!”或“NO!”，但并不输出“路线图”）。
（2）若更改程序中的n值（如改为4或6等），便可求解其他阶数的巡游“路线图”。
（3）可改用非递归方法设计并编写solve函数，那样的话，通常要增加一个记录摆放“棋子”信息的数组，可记录下是沿着什么方向到达了当前的什么位置（在那儿摆放了“棋子”）等，而且对上述数组可按照栈（stack）的方式来使用（栈总是采用FILO即所谓的先进后出使用方式），以便在“无路可走”的情况下，回退（回溯）到上一个位置，接着按照另外的方向去寻找其他的“行走”方法。

Answer 1

#include <iostream.h>
#include <stdio.h>
int map[9][9];//用来标记的二维数组
int n=5;//实际计算时的棋盘大小，超过5时运算时间过长，小于5时无解
class Knight{
private:
int dirx[8];//八个方向可以走，用两个数组分别记录每个方向上x,y的坐标位移
int diry[8];
public:
Knight(){
dirx[0]=1;diry[0]=2;
dirx[1]=2;diry[1]=1;
dirx[2]=1;diry[2]=-2;
dirx[3]=2;diry[3]=-1;
dirx[4]=-1;diry[4]=2;
dirx[5]=-2;diry[5]=1;
dirx[6]=-1;diry[6]=-2;
dirx[7]=-2;diry[7]=-1;
}
private:
bool judge(int y,int x){
if(x>0 && x<=n && y>0 && y<=n && map[y][x]==0)
return true;
else
return false;
}
public:
void set(int y,int x,int t){
if(t==n*n){
map[y][x]=t;
cout<<"one possible answer:"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][j]<10)
cout<<" ";
cout<<" "<<map[i][j];
}
cout<<endl<<endl;
}
map[y][x]=0;
return;
}
else{
if(map[y][x]==0){
map[y][x]=t;
int nextt=t+1;
for(int i=0;i<8;i++){
if(judge(y+diry[i],x+dirx[i]))
set(y+diry[i],x+dirx[i],nextt);
}
map[y][x]=0;
}
}
}
};
void main(){
Knight *horse=new Knight();//骑士也要走马步
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
map[i][j]=0;
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
horse->set(i,j,1);
delete horse;
}

//运行后会输出可能的步骤
//楼主加分吧