题目链接：poj1915 Knight Moves
比起单向要省时得多。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=310;
const int INF=0x3f3f3f3f;
typedef long long ll;int dir[8][2]={
{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
int vis[maxn][maxn],sx,sy,tx,ty,n,cnt,mp[maxn][maxn];typedef struct Node{int x,y,step;
}Node;void dbfs(){memset(vis,0,sizeof(vis));memset(mp,0,sizeof(mp));cnt=0;queue<Node>q0,q1;Node tmp,nxt;tmp.x=sx,tmp.y=sy,tmp.step=0;vis[sx][sy]=2;q0.push(tmp);tmp.x=tx,tmp.y=ty,tmp.step=0;vis[tx][ty]=1;q1.push(tmp);while(!q0.empty()||!q1.empty()){if(!q0.empty()){tmp=q0.front();q0.pop();for(int i=0;i<8;i++){nxt.x=tmp.x+dir[i][0];nxt.y=tmp.y+dir[i][1];nxt.step=tmp.step+1;if(nxt.x>=n||nxt.x<0||nxt.y>=n||nxt.y<0||vis[nxt.x][nxt.y]==2) continue;if(vis[nxt.x][nxt.y]==1){cnt=nxt.step+mp[nxt.x][nxt.y];return ;}vis[nxt.x][nxt.y]=2;mp[nxt.x][nxt.y]=nxt.step;q0.push(nxt);}}if(!q1.empty()){tmp=q1.front();q1.pop();for(int i=0;i<8;i++){nxt.x=tmp.x+dir[i][0];nxt.y=tmp.y+dir[i][1];nxt.step=tmp.step+1;if(nxt.x>=n||nxt.x<0||nxt.y>=n||nxt.y<0||vis[nxt.x][nxt.y]==1) continue;if(vis[nxt.x][nxt.y]==2){cnt=nxt.step+mp[nxt.x][nxt.y];return ;}vis[nxt.x][nxt.y]=1;mp[nxt.x][nxt.y]=nxt.step;q1.push(nxt);}}}
}int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);scanf("%d%d%d%d",&sx,&sy,&tx,&ty);if(sx==tx&&sy==ty){printf("0\n");}else{dbfs();printf("%d\n",cnt);}}return 0;
}