骑士巡游问题Java代码,骑士巡游问题java代码是多少

. 编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从

这个是我之前做的算法，但然我也是参考了网上提供的思想来做的。这个思想很广泛。把你输入的一个点为第一步，接着搜他可走8个方向中每一个可走的点，并记录这样可走的点的位置。再把这些记录的点再搜他可走的8个方向，但这些只要记录8个方向中可走方向的数目。接着就走方向最少的一条路。这样难走的路在前面已经走了，后面的路就好走很多了，一般都能找到方向。当然还有递归这种算法，但高维度的递归是没有意议的，电脑是算不出来的或着用很长时间才能算出来。下面是我的算法

#includeiostream

using namespace std;

//定义棋盘的大小

#define N 8

#define LOSE 0

#define SUCCEED 1

void printknightgo(); //输出结果

int knightgo(int x,int y); //运算走法

int chessboard[8][8] = { 0 }; //建立棋盘

void main(){

int x,y;

cout"请输入坐标"endl;

cinxy; //输入坐标

if(knightgo(x,y)){ //开始运算走法，如果成功则返回成功，否则返回失败

cout"成功完成"endl;

}

else{

cout"失败"endl;

}

printknightgo(); //输出结果

}

//输出结果的算法

void printknightgo(){

for(int i = 0;i N; i++){

for(int j = 0;j N;j++){

coutchessboard[i][j]"\t";

}

coutendl;

}

}

int knightgo(int x,int y){

chessboard[x][y] = 1;//将第一步标为1

int step;//走的步数

int nextx[8] = {-1,1,-2,2,-2,2,-1,1};//走的X的步法

int nexty[8] = {2,2,1,1,-1,-1,-2,-2};//走的Y的步法

int recordNextx[8]={0};//记住下步可走X的位置，并用count来记数

int recordNexty[8]={0};//记住下步可走Y的位置，并用count来记数

int tempx,tempy;//用于临时记住X和Y

int i,j;//临时计数变量

int count = 0;//记住可循环的个数

int exist[8]={0};//第2次找8个方向每个可走的记录

for(int step = 2;step =N*N;step++){//把输进来或循环的位置，找下一个能走的位置,并记住这些位置和可走的个数

for(i = 0;i 8;i++){ //把上次记录重置0;

recordNextx[i] = 0;

recordNexty[i] = 0;

exist[i] = 0;

}

count = 0;

for(i = 0;i 8;i++){//第一次循环，找可走的个位置，并记录可走方向的个数

tempx = x + nextx[i];//tempx为临时记录X

tempy = y + nexty[i];//tempy为临时记录Y

if(chessboard[tempx][tempy] == 0 tempx = 0 tempx N tempy = 0 tempy N){//当这个位置没走过和不走出盘外时，才能记录

recordNextx[count] = tempx;

recordNexty[count] = tempy;//记录可走方向的x,y坐标

count++; //记录可以走的方向的个数

}

}

//把记住的位置,找他们的下个能走位置的个数,就是重复上面循环，只需记录可走方向的个数

if(count == 0){//如果没有出路则返回失败

return LOSE;

}

else {//如果只有一条路，则走这一条路

if(count == 1){

x = recordNextx[0];//因为可走方向只有一个，所记录中就有recordNext(x,y)[0];

y = recordNexty[0];

chessboard[x][y] = step; //把第几步写入这个棋盘的位置

}

else{//有多条路可以走的话

for(j = 0;j count;j++){//第一个点记录的可走的方向，并找出们下一个方向可以走的的方向的个数

for(i = 0;i 8;i++){//找第2个点8个方向可走的方向

tempx = recordNextx[j] + nextx[i];

tempy = recordNexty[j] + nexty[i];

if(chessboard[tempx][tempy] == 0 tempx = 0 tempx N tempy = 0 tempy N){//当这个位置没走过和不走出盘外时，才能记录

exist[j]++;//记录第2个点可走方向的个数

}

}

}

//找最方向个数最小的一条路

int min = exist[0];

int last = 0;//用于记住，recordNext(x,y)中可走方向中，能走方向数目最小的一个方向

for(i = 1;i count;i++){//找出方向数目最小的数和方向

if(exist[i]min){

min = exist[i];

last = i;

}

}

x = recordNextx[last];//将这个方向给x,y;

y = recordNexty[last];

chessboard[x][y] = step; //将这个步数写出这个棋盘

}

}

}

return SUCCEED;

}

相关问答

Q1: 骑士巡游问题 pascal 急！！！

楼上的程序太麻烦，效率低

【骑士游历问题】

设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。

输入：

m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)

输出：

路径数目（若不存在，则输出0）

【分析】

本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。（专为楼下设计）

从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。

阶段i：中国象棋马当前的列位置（x1≤i≤x2）

状态j：中国象棋马在i列的行位置（1≤i≤m）

状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目

附标程：

const

maxm=50;

maxn=50;

var

m,n,x1,y1,x2,y2:integer;

i,j,k,x,y:integer;

map:array[-2..maxm+2,-2..maxn+2] of extended;

begin

fillchar(map,sizeof(map),0);

readln(m,n,x1,y1,x2,y2);

map[x1,y1]:=1;

for i:=x1+1 to x2 do

for j:=1 to m do

map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];

writeln(map[x2,y2]:0:0);

end.

搜索比较慢，有代码如下：

program p7_1;

const dx:array[1..8] of integer=(1,-1,-2,-2,-1,1,2,2);

dy:array[1..8] of integer=(2,2,-1,-1,-2,-2,-1,1);

var board:array[-1..7,-1..7] of integer;

t,i,j,a,b:integer;

procedure search(t,x,y:integer);

var p,m,n:integer;

begin

if t=26 then begin

for m:=1 to 5 do begin

for n:=1 to 5 do write(board[m,n]:3);

writeln;

end;

t:=-1;

halt

end;

if board[x,y]=0 then begin

board[x,y]:=t;inc(t);

for p:=1 to 8 do search(t,x+dx[p],y+dy[p]);

board[x,y]:=0;

end;

end;

begin

t:=1;

for i:=-1 to 7 do

for j:=-1 to 7 do board[i,j]:=-1;

for a:=1 to 5 do

for b:=1 to 5 do board[a,b]:=0;

search(t,1,1);

if t-1 then write('Wrong!');

end.

Q2: C++中怎样非递归实现骑士巡游问题？急求代码！

#include iostream 

#include iomanip  //setw()的头文件 

#define N 5        //定义一个宏并赋初值 

using namespace std;

struct xy

{

int x;

int y;

int odr;

};

int b[N][N];    //定义全局性的二维数组保存步数 

bool a[N][N];   //记录某一点是否已经走过 

xy setp[N*N + 1];

int num = 0;      //记录方案数 

int dx[] = { 0, 1, 1, -1, -1, 2, 2, -2, -2 };

int dy[] = { 0, 2, -2, 2, -2, 1, -1, 1, -1 };  //提供每一步的走法 

void solve(int i, int j, int k, boolok)  //计算走法 

{

int m, x1, y1, n1, n2;

bool t1, t2;

setp[1].x = i;

setp[1].y = j;

for (k=2; k = N*Nk = 2; k++)//8 个方向

{

for (m = setp[k].odr; m = 8; m++)//8 个方向

{

x1 = setp[k - 1].x + dx[m];

y1 = setp[k - 1].y + dy[m];

t1 = ((x1 = 0)  (x1  N));  //判断x是否在棋盘内 

t2 = ((y1 = 0)  (y1  N));  //判断y是否在棋盘内 

if ((t1 == true)  (t2 == true)  (a[x1][y1] == true))

{

a[x1][y1] = false;  //记录该点已经走过 

b[x1][y1] = k;//步数

setp[k].x = x1;

setp[k].y = y1;

setp[k].odr = m;

if (k = N*N)

{

num++;     //方案数加一 

ok = true;

//输出

cout  "方案"  num  " :"  endl;

for (n1 = 0; n1  N; n1++)

{

for (n2 = 0; n2  N; n2++)

{

cout  setw(4)  b[n1][n2]; //依次输出经过每一点时的步数 

}

cout  endl;

}

//if (num % 10 == 0) getchar();

//return; 

a[setp[k].x][setp[k].y] = true;

//b[setp[k ].x][setp[k ].y] = 0;//步数

setp[k].odr++;

//  setp[k].x = 0;

//  setp[k].y = 0;

k -= 1;

}//退一步

break;

}

}

if (m  8){

a[setp[k - 1].x][setp[k - 1].y] = true;

//b[setp[k-1].x][setp[k-1].y] = 0;//步数;

setp[k].odr = 1;

setp[k - 1].odr++;

k -= 2;

}

}

}

int main()

{

int i, j, row, col;

bool ok = false;

for (i = 0; i  N; i++)

{

for (j = 0; j  N; j++)

a[i][j] = true;

}

cout  "请输入起始位置的坐标:";

cin  row  col;

b[row - 1][col - 1] = 1; //设置起始点 

a[row - 1][col - 1] = false;

solve(row - 1, col - 1, 2, ok);  //调用函数计算结果 

if (!ok)

cout  "从点("  row  ","  col  ")出发无法遍访棋盘的每一个位置"  endl;

return 0;

}

Q3: 骑士巡游问题时间复杂度是多少

楼上的程序太麻烦，效率低【骑士游历问题】 设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。输入： m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)输出： 路径数目（若不存在，则输出0）【分析】 本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。（专为楼下设计） 从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。 阶段i：中国象棋马当前的列位置（x1≤i≤x2） 状态j：中国象棋马在i列的行位置（1≤i≤m） 状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目附标程：const maxm=50; maxn=50;var m,n,x1,y1,x2,y2:integer; i,j,k,x,y:integer; map:array[-2..maxm+2,-2..maxn+2] of extended;beginfillchar(map,sizeof(map),0);readln(m,n,x1,y1,x2,y2);map[x1,y1]:=1;for i:=x1+1 to x2 do for j:=1 to m do map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];writeln(map[x2,y2]:0:0);end. 搜索比较慢，有代码如下：program p7_1;const dx:array[1..8] of integer=(1,-1,-2,-2,-1,1,2,2); dy:array[1..8] of integer=(2,2,-1,-1,-2,-2,-1,1);var board:array[-1..7,-1..7] of integer; t,i,j,a,b:integer;procedure search(t,x,y:integer);var p,m,n:integer;begin if t=26 then begin for m:=1 to 5 do begin for n:=1 to 5 do write(board[m,n]:3); writeln; end; t:=-1; halt end; if board[x,y]=0 then begin board[x,y]:=t;inc(t); for p:=1 to 8 do search(t,x+dx[p],y+dy[p]); board[x,y]:=0; end;end;begin t:=1; for i:=-1 to 7 do for j:=-1 to 7 do board[i,j]:=-1; for a:=1 to 5 do for b:=1 to 5 do board[a,b]:=0; search(t,1,1); if t-1 then write('Wrong!');end.

Q4: C++ 骑士巡游问题 救急！！！ 帮忙看看代码 修改一下！

你其实巡游的第一步是(0,0)，就是不动，应该会递归致死吧。

还有，你的s[][]有更改过值么？那个是记录走过的格子的吧。

Q5: 骑士巡游问题

没做过，看过。“骑士总是移向具有最少出口且没有到达过的方格之一”是说，它可移动的位置有N个，在这N个中，寻找下一次可移动的位置最少的那个，做为骑士要去的点的位置。这是一种贪婪法，有的位置有解但你却求不出来。