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

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

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

创新互联主要从事成都网站制作、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务兖州,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

#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;

}

骑士巡游问题 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;

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.

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;

}

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

楼上的程序太麻烦，效率低【骑士游历问题】设有一个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.

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

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

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