请问"骑士旅行"的算法在JAVA里是如何实现的? 這個好像不是算法問題,難道在c/c++/java/basic中這個算法就不同了嗎? 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 哪有在C/C++/Java/Basic就不同之理!转载 作者:杨志斌C之骑士旅行迷宫算法!————照着改吧!// 骑士旅行之迷宫算法//程序马骑士旅行路线想像成一个迷宫,利用堆栈存储一条正确路线。//结合游戏玩家的无敌玩法,即打胜了存档,打输了调档,最终自然是只赢不输。//本程序也一样,走对存档,走错了调档,最终自然是会找到正确路线。#include"iostream.h"#include"stdio.h"#define STP 55 //骑士旅行步数,一般取50到58步之间,取64步调试时间太长//定义点变量类形typedef struct{int x;int y;int z;} NONCE;//函数原数int startpd(NONCE [8][8],NONCE); //起点判断NONCE next(NONCE); //试探下一步函数void save(NONCE [8][8],NONCE [100],int); //存档void load(NONCE [8][8],NONCE [100],int); //读档int bjpd(NONCE); //边界判断int hfpd(NONCE [8][8],NONCE); //合法点判断//程序入口int main(){NONCE chess[8][8]; //定义棋盘,行列表示格子,成员x表示棋盘步数,成员z表示下一步将要试探的地方 //由于骑士最多只能走八个方向,故z值只能取 0 ~ 7 int i,j,k;NONCE start; for(i=0;i<8;i++) for(j=0;j<8;j++) { start.x=i;start.y=j;start.z=0; if(startpd(chess,start))goto endfor; //起点判断,如果该点可以为起点则返回1 //否则返回0 }endfor: //输出 for(i=0;i<8;i++) { for(j=0;j<8;j++) { if(chess[i][j].x==-1) //骑士没有走的地方显示 "@" cout << "@ "; else printf("%2d ",chess[i][j].x); //骑士走过的地方显示所走的是第几步 } cout << endl << endl; }return 0;} //end main//起点判断,如果该点可以为起点则返回1//否则返回0int startpd(NONCE chess[8][8],NONCE start){NONCE stack[100]; //定义堆栈 NONCE nexttmp;int point;int i,j,k;//将棋盘清空 for(i=0;i<8;i++) for(j=0;j<8;j++) { chess[i][j].x=-1; chess[i][j].y=0; chess[i][j].z=0; }//将堆栈清空 for(i=0;i<100;i++) { stack[i].x=0; stack[i].y=0; stack[i].z=0; }//将起点赋值给栈底 point=0; stack[point].x=start.x; stack[point].y=start.y; stack[point].z=start.z; do{ nexttmp=next(stack[point]); //试探下一步 if(hfpd(chess,nexttmp)) //判断试探的下一步是否合法 { point++; //如果合法,则存档 stack[point]=nexttmp; save(chess,stack,point); //存档 } else if(stack[point].z<7) //如果不合法,则判断8种走法是否走完 { //如果没走完,则继续试探下一种走法 stack[point].z++; } else { point--; //如果8种走法都走完还是没有出路,则已表示该点 //为死点,退回到上一步继续试探,即像游戏玩家那调档 load(chess,stack,point); //读档 stack[point].z++; } if(stack[0].z>=8)return 0; //如果栈底的8种走都已走完,则表示该点不能作为起点,函数返回0 cout << " " << point << endl; }while(point<=STP); //如果已走完指定的步数,退出试探,函数返回1return 1;} //end startpd//存档函数void save(NONCE chess[8][8],NONCE stack[100],int point){int i,j,k; for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;} for(k=0;k<=point;k++) { chess[stack[k].x][stack[k].y].x=k; chess[stack[k].x][stack[k].y].y=0; chess[stack[k].x][stack[k].y].z=stack[k].z; }} //end save//读档函数void load(NONCE chess[8][8],NONCE stack[100],int point){int i,j,k; for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;} for(k=0;k<=point;k++) { chess[stack[k].x][stack[k].y].x=k; chess[stack[k].x][stack[k].y].y=0; chess[stack[k].x][stack[k].y].z=stack[k].z; }}//end load//试探下一步点函数NONCE next(NONCE non){NONCE nex;begin: if(non.z==0) { nex.x=non.x+2; nex.y=non.y-1; } else if(non.z==1) { nex.x=non.x+1; nex.y=non.y-2; } else if(non.z==2) { nex.x=non.x-1; nex.y=non.y-2; } else if(non.z==3) { nex.x=non.x-2; nex.y=non.y-1; } else if(non.z==4) { nex.x=non.x-2; nex.y=non.y+1; } else if(non.z==5) { nex.x=non.x-1; nex.y=non.y+2; } else if(non.z==6) { nex.x=non.x+1; nex.y=non.y+2; } else if(non.z==7) { nex.x=non.x+2; nex.y=non.y+1; } nex.z=0; if(bjpd(nex)) { non.z++; goto begin; }return nex;} // end nextpd//边界判断函数int bjpd(NONCE nex){if(nex.x<0||nex.x>7||nex.y<0||nex.y>7) return 1;else return 0;}//end bjpd//合法点判断函数int hfpd(NONCE chess[8][8],NONCE non){if(chess[non.x][non.y].x==-1) return 1;else return 0;} // end nextpd [email protected] 在一个n*m 格子的棋盘上,有一只国际象棋的骑士在棋盘的左下角 (1;1),骑士只能根据象棋的规则进行移动,要么横向跳动一格纵向跳动两格,要么纵向跳动一格横向跳动两格。 例如, n=4,m=3 时,若骑士在格子(2;1) , 则骑士只能移入下面格子:(1;3),(3;3) 或 (4;2);对于给定正整数n,m,I,j值 (m,n<=50,I<=n,j<=m) ,你要测算出从初始位置(1;1) 到格子(i;j)最少需要多少次移动。如果不可能到达目标位置,则输出"NEVAR"。 输入(Horse.in): 输入文件的第一行为两个整数n与m,第二行为两个整数i与j。 输出(Horse.out): 输出文件仅包含一个整数为初始位置(1;1) 到格子(i;j)最少移动次数。 样例1: Horse.in Horse.out 5 3 3 1 2 ------------------------------------------------------------------[email protected]------------------------------------------------------------------ 其实问题是这样的: 骑士这枚棋子在空棋盘上到处移动,能否经过64个方格且在每个方格上只经过一次?骑士在棋盘上做L形运动( 在一个方向上走过两格然后在垂直的方向上走一格式化).因此,从一个空棋盘的中间开始,骑士可有8种不同的移动.编写一个程序,使骑士在棋盘上旅行,找出一条能走完64个格的路线.骑士从一个点开始可以到达N个点(N<9),但那N个点又可以到达N个点,我不知应该如何控制"骑士"选择路线并记录~~~我只学到数组,而这个问题是在数组那章的,是不是只用数组就能解决此问题呢?有人能提供JAVA版给我看看吗? 看不懂这个问题,也想不通,请大侠帮帮忙 先谢了 问:有没有关于背景颜色羽化效果的方法 求助:怎样理解如下的方法调用? java 中文件操作问题????????????? 为什么一调用java命令就出现这个异常啊? 别人做了个暴强的软件,我也想做,就是毫无头绪,想知道的进来,内详. 请问哪里有JAVA学习的好中文网站 我的setDefaultClouseOperation()错在哪? HttpClient 怎么保持多个请求中Session是唯一的! 谁懂这个问题! 指挥系统的数据传输解决方案? MYSQL的问题,在线等回复
转载 作者:杨志斌C之骑士旅行迷宫算法!————照着改吧!// 骑士旅行之迷宫算法
//程序马骑士旅行路线想像成一个迷宫,利用堆栈存储一条正确路线。
//结合游戏玩家的无敌玩法,即打胜了存档,打输了调档,最终自然是只赢不输。
//本程序也一样,走对存档,走错了调档,最终自然是会找到正确路线。#include"iostream.h"
#include"stdio.h"
#define STP 55 //骑士旅行步数,一般取50到58步之间,取64步调试时间太长
//定义点变量类形
typedef struct
{
int x;
int y;
int z;
} NONCE;//函数原数
int startpd(NONCE [8][8],NONCE); //起点判断
NONCE next(NONCE); //试探下一步函数
void save(NONCE [8][8],NONCE [100],int); //存档
void load(NONCE [8][8],NONCE [100],int); //读档
int bjpd(NONCE); //边界判断
int hfpd(NONCE [8][8],NONCE); //合法点判断//程序入口
int main()
{
NONCE chess[8][8]; //定义棋盘,行列表示格子,成员x表示棋盘步数,成员z表示下一步将要试探的地方
//由于骑士最多只能走八个方向,故z值只能取 0 ~ 7
int i,j,k;
NONCE start;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
start.x=i;start.y=j;start.z=0;
if(startpd(chess,start))goto endfor; //起点判断,如果该点可以为起点则返回1
//否则返回0
}
endfor:
//输出
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(chess[i][j].x==-1) //骑士没有走的地方显示 "@"
cout << "@ ";
else
printf("%2d ",chess[i][j].x); //骑士走过的地方显示所走的是第几步
}
cout << endl << endl;
}
return 0;
} //end main
//起点判断,如果该点可以为起点则返回1
//否则返回0
int startpd(NONCE chess[8][8],NONCE start)
{
NONCE stack[100]; //定义堆栈
NONCE nexttmp;
int point;
int i,j,k;//将棋盘清空
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
chess[i][j].x=-1;
chess[i][j].y=0;
chess[i][j].z=0;
}//将堆栈清空
for(i=0;i<100;i++)
{
stack[i].x=0;
stack[i].y=0;
stack[i].z=0;
}//将起点赋值给栈底
point=0;
stack[point].x=start.x;
stack[point].y=start.y;
stack[point].z=start.z;
do{
nexttmp=next(stack[point]); //试探下一步
if(hfpd(chess,nexttmp)) //判断试探的下一步是否合法
{
point++; //如果合法,则存档
stack[point]=nexttmp;
save(chess,stack,point); //存档
}
else if(stack[point].z<7) //如果不合法,则判断8种走法是否走完
{ //如果没走完,则继续试探下一种走法
stack[point].z++;
}
else
{
point--; //如果8种走法都走完还是没有出路,则已表示该点
//为死点,退回到上一步继续试探,即像游戏玩家那调档
load(chess,stack,point); //读档
stack[point].z++;
} if(stack[0].z>=8)return 0; //如果栈底的8种走都已走完,则表示该点不能作为起点,函数返回0
cout << " " << point << endl;
}while(point<=STP); //如果已走完指定的步数,退出试探,函数返回1
return 1;
} //end startpd//存档函数
void save(NONCE chess[8][8],NONCE stack[100],int point)
{
int i,j,k; for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}
for(k=0;k<=point;k++)
{
chess[stack[k].x][stack[k].y].x=k;
chess[stack[k].x][stack[k].y].y=0;
chess[stack[k].x][stack[k].y].z=stack[k].z;
}
} //end save//读档函数
void load(NONCE chess[8][8],NONCE stack[100],int point)
{
int i,j,k;
for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}
for(k=0;k<=point;k++)
{
chess[stack[k].x][stack[k].y].x=k;
chess[stack[k].x][stack[k].y].y=0;
chess[stack[k].x][stack[k].y].z=stack[k].z;
}
}//end load//试探下一步点函数
NONCE next(NONCE non)
{
NONCE nex;
begin:
if(non.z==0)
{
nex.x=non.x+2;
nex.y=non.y-1;
}
else if(non.z==1)
{
nex.x=non.x+1;
nex.y=non.y-2;
}
else if(non.z==2)
{
nex.x=non.x-1;
nex.y=non.y-2;
}
else if(non.z==3)
{
nex.x=non.x-2;
nex.y=non.y-1;
}
else if(non.z==4)
{
nex.x=non.x-2;
nex.y=non.y+1;
}
else if(non.z==5)
{
nex.x=non.x-1;
nex.y=non.y+2;
}
else if(non.z==6)
{
nex.x=non.x+1;
nex.y=non.y+2;
}
else if(non.z==7)
{
nex.x=non.x+2;
nex.y=non.y+1;
}
nex.z=0;
if(bjpd(nex))
{
non.z++;
goto begin;
}
return nex;
} // end nextpd
//边界判断函数
int bjpd(NONCE nex)
{
if(nex.x<0||nex.x>7||nex.y<0||nex.y>7)
return 1;
else
return 0;
}//end bjpd//合法点判断函数
int hfpd(NONCE chess[8][8],NONCE non)
{
if(chess[non.x][non.y].x==-1)
return 1;
else
return 0;
} // end nextpd
[email protected]
输入(Horse.in):
输入文件的第一行为两个整数n与m,第二行为两个整数i与j。 输出(Horse.out):
输出文件仅包含一个整数为初始位置(1;1) 到格子(i;j)最少移动次数。 样例1:
Horse.in Horse.out
5 3 3
1 2 ------------------------------------------------------------------
[email protected]
------------------------------------------------------------------
骑士这枚棋子在空棋盘上到处移动,能否经过64个方格且在每个方格上只经过一次?骑士在棋盘上做L形运动( 在一个方向上走过两格然后在垂直的方向上走一格式化).因此,从一个空棋盘的中间开始,骑士可有8种不同的移动.编写一个程序,使骑士在棋盘上旅行,找出一条能走完64个格的路线.骑士从一个点开始可以到达N个点(N<9),但那N个点又可以到达N个点,我不知应该如何控制"骑士"选择路线并记录~~~我只学到数组,而这个问题是在数组那章的,是不是只用数组就能解决此问题呢?有人能提供JAVA版给我看看吗?