编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
5
28
0
分析
这道题是一道广搜题，用深搜可能会时间超限。这道题难度也不低，代码很长，需要用到队列queue
代码
#include<bits/stdc++.h> using namespace std; bool vis[301][301]; int step[301][301],ans,t,n,sx,sy,ex,ey,nx,ny; int main() { scanf("%d",&t); while(t--){ scanf("%d%d%d%d%d",&n,&sx,&sy,&ex,&ey); queue<int> qx,qy; qx.push(sx),qy.push(sy); vis[sx][sy]=1; step[sx][sy]=0; while(!qx.empty()&&!qy.empty()){ nx=qx.front(),qx.pop(); ny=qy.front(),qy.pop(); if(nx==ex&&ny==ey){ ans=step[ex][ey];//如果达到终点，则停止 break; } if(nx-2>=0&&ny+1<=n&&vis[nx-2][ny+1]==0)//八个方向开始搜索 { qx.push(nx-2); qy.push(ny+1); step[nx-2][ny+1]=step[nx][ny]+1; vis[nx-2][ny+1]=1; } if(nx-2>=0&&ny-1>=0&&vis[nx-2][ny-1]==0) { qx.push(nx-2); qy.push(ny-1); step[nx-2][ny-1]=step[nx][ny]+1; vis[nx-2][ny-1]=1; } if(nx-1>=0&&ny+2<=n&&vis[nx-1][ny+2]==0) { qx.push(nx-1); qy.push(ny+2); step[nx-1][ny+2]=step[nx][ny]+1; vis[nx-1][ny+2]=1; } if(nx-1>=0&&ny-2>=0&&vis[nx-1][ny-2]==0) { qx.push(nx-1); qy.push(ny-2); step[nx-1][ny-2]=step[nx][ny]+1; vis[nx-1][ny-2]=1; } if(nx+1<=n&&ny+2<=n&&vis[nx+1][ny+2]==0) { qx.push(nx+1); qy.push(ny+2); step[nx+1][ny+2]=step[nx][ny]+1; vis[nx+1][ny+2]=1; } if(nx+2<=n&&ny+1<=n&&vis[nx+2][ny+1]==0) { qx.push(nx+2); qy.push(ny+1); step[nx+2][ny+1]=step[nx][ny]+1; vis[nx+2][ny+1]=1; } if(nx+2<=n&&ny-1>=0&&vis[nx+2][ny-1]==0) { qx.push(nx+2); qy.push(ny-1); step[nx+2][ny-1]=step[nx][ny]+1; vis[nx+2][ny-1]=1; } if(nx+1<=n&&ny-2>=0&&vis[nx+1][ny-2]==0) { qx.push(nx+1); qy.push(ny-2); step[nx+1][ny-2]=step[nx][ny]+1; vis[nx+1][ny-2]=1; } } printf("%d\n",ans); memset(vis,0,sizeof(vis));//因为有多组样例，所以需要置零 memset(step,0,sizeof(step)); nx=0,ny=0,ans=0; while(!qx.empty()&&!qy.empty()){//清空队列 qx.pop(); qy.pop(); } } return 0; }
原文：https://www.cnblogs.com/earth833/p/11168292.html