Question

各位高手请帮小女子解决一下这个骑士巡游问题,苦恼了我很久.

/*
编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中"马走日"的行走法）
从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡
游"路线图"（或告诉骑士，从某位置出发时，无法遍访整个棋盘 - 问题无解）。

当n=5时，意味着要在5行5列的棋盘的25个"点"处，按骑士行走规则，依次将1至25这25个"棋子"（数码）
分别摆放到棋盘上（摆满25个位置则成功，否则失败问题无解）。
*/
#include<iostream>
#include <iomanip>
using namespace std;

//最多8个端口时x,y坐标的增量
int x_increase[]={-2,-2,-1,1,2,2,1,-1};
int y_increase[]={-1,1,2,2,1,-1,-2,-2};

int check[5][5];
int i,j,k;
int s[25]; //记录行走每一步的端口号(0-7)
bool ok=true;
//从（i，j）点出发，做第k至第n*n次移动，若全部成功则返回ok为ture，否则为false
void solve(int i,int j,int k,bool& ok)
{

int dk;
// bool ok=true;
if(k==25)return;
if(k<0)
{
cout<<"无解";
exit(0);
}
//for(;k<25;k++)
//{
if(ok) dk=0;
if(ok==false)dk=s[k]+1;
for(;dk<8;dk++)
{
if((i+x_increase[dk])<5&&(i+x_increase[dk])>=0&&(j+y_increase[dk])<5&&(j+y_increase[dk])>=0&&check[i+x_increase[dk]][j+y_increase[dk]]==0)
{
i=i+x_increase[dk];
j=j+y_increase[dk];
check[i][j]=k+1;

s[k]=dk;
ok=true;
solve(i,j,k+1,ok);
break;
}
}
if(dk==8)
{
k=k-1;
check[i][j]=0;
//check[i-x_increase[]][]=1;
i=i-x_increase[s[k]];
j=j-y_increase[s[k]];
ok=false;
solve(i,j,k,ok);
}
}

void print()
{
for( i=0;i<5;i++)
{
for( j=0;j<5;j++)
{
cout<<setw(6)<<check[i][j]<<" ";
}
cout<<'\n';
}
}

void main()
{
for(i=0;i<5;i++)
for(j=0;j<5;j++)
check[i][j]=0; //初始化棋盘,未走过的地方全都设为0

cout<<"输入从第几排,几列开始巡游"<<endl;
cout<<"行";
cin>>i;
cout<<"列";
cin>>j;
cout<<endl;
if(i<1||i>5||j<1||j>5)
{
cout<<"输入错误！"<<endl;
return ;
}
i=i-1;
j=j-1;
k=0;
check[i][j]=1;
//ok=true;
solve(i,j,k+1,ok);
print();
return;
}

/*只有一行一列的时候才能执行,可我觉得自己没错.可调试的时候也出现了很奇怪的事,可我不明白是什么意思.谢谢各位了.*/

Answer 1

solve递归条件好像有点问题

//这是我以前记下的,但不知道作者是谁了...（侵权了）
#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;
}

Answer 2

DFS么???

Answer 3

你都不给分 是女的也不能这样