13518219792
这个是我之前做的算法，但然我也是参考了网上提供的思想来做的。这个思想很广泛。把你输入的一个点为第一步，接着搜他可走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;
}
楼上的程序太麻烦，效率低
【骑士游历问题】
设有一个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.
#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.
你其实巡游的第一步是(0,0)，就是不动，应该会递归致死吧。
还有，你的s[][]有更改过值么？那个是记录走过的格子的吧。
没做过，看过。“骑士总是移向具有最少出口且没有到达过的方格之一”是说，它可移动的位置有N个，在这N个中，寻找下一次可移动的位置最少的那个，做为骑士要去的点的位置。这是一种贪婪法，有的位置有解但你却求不出来。
