【题目描述】

编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。

【算法】

双向bfs优先扩展节点数少的队列。什么破东西速度没快多少啊。。。。

【代码】

#include 
    
     #include 
     
      #define P pair
      
       #define ff first#define ss secondusing namespace std;int T,ans,L;int d[310][310][2];const int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1};queue
       
 q[2];bool work(int x,queue
       
& q) {    P now=q.front(); q.pop();    for(int i=0;i<8;i++) {        int nx=now.ff+dx[i],ny=now.ss+dy[i];        if(nx>=1&&nx<=L&&ny>=1&&ny<=L&&d[nx][ny][x]==-1) {            d[nx][ny][x]=d[now.ff][now.ss][x]+1;            if(d[now.ff][now.ss][x^1]!=-1) {                ans=d[now.ff][now.ss][0]+d[now.ff][now.ss][1];                return 1;            }            q.push(make_pair(nx,ny));        }    }    return 0;}int main() {    scanf("%d",&T);    while(T--) {        scanf("%d",&L);        P x; scanf("%d%d",&x.ff,&x.ss); x.ff++,x.ss++;        P y; scanf("%d%d",&y.ff,&y.ss); y.ff++,y.ss++;        for(int i=1;i<=L;i++)            for(int j=1;j<=L;j++)                d[i][j][0]=d[i][j][1]=-1;        queue
       
 q[2];        q[0].push(x),d[x.ff][x.ss][0]=0;        q[1].push(y),d[y.ff][y.ss][1]=0;        while(q[0].size()&&q[1].size()) {            if(q[0].size()