这一题主要用到了BFS广度优先算法 若马的当前位置为(x,y),那么下一步就有8种可能。
(x+2 , y+1) , (x+1 , y+2 ) , (x-1 , y+2) , (x-2 , y+1)
(x+2 , y -1) , (x+1 , y-2 ) , (x-1 , y-2) , (x-2 , y-1)
这8种可能一个一个地去尝试，尝试过的用visit二维数组标记（小心数组越界），直到找到为止。
#include <iostream>
#include <string.h>
using namespace std;
struct Node{
public:
int x,y,d;
};
Node n[90010]; //可以用queue函数去做
int visit[310][310];
int step[8][2]={{-1,-2},{-1,2},{1,-2},{1,2},{-2,-1},{-2,1},{2,-1},{2,1}};
int bfs(Node source,Node target,int l){
int i=0,j=0,d=0,nx,ny,x,y;
memset(visit,0,sizeof(visit));
n[0].x=source.x;
n[0].y=source.y;
n[0].d=source.d=0;
visit[source.x][source.y]=1;
while(j<=i){
x=n[j].x;
y=n[j].y;
d=n[j].d+1;
j++;
for(int k=0;k<8;k++){
nx=x+step[k][0];
ny=y+step[k][1];
if(nx<0||ny<0||nx>l-1||ny>l-1)continue; //注意题目要求为0~L-1
if(visit[nx][ny])continue;
if(nx==target.x&&ny==target.y)return d;
i++;
n[i].x=nx;
n[i].y=ny;
n[i].d=d;
visit[nx][ny]=1;
}
}
return 0;
}
int main()
{ int t,l;
cin>>t;
Node source,target;
while(t--){
cin>>l>>source.x>>source.y>>target.x>>target.y;
if(source.x==target.x&&source.y==target.y)cout<<"0"<<endl;
else cout<<bfs(source,target,l)<<endl;
}
return 0;
}