Knight Moves （双向bfs）

# 10028. 「一本通 1.4 例 3」Knight Moves

【题目描述】

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

【算法】

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

【代码】

#include <stdio.h>

#include <queue>

#define P pair<int,int>

#define ff first

#define ss second

using 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<P> q[2];

bool work(int x,queue<P>& 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<P> 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()<q[1].size()) {

                if(work(0,q[0])) break;

            }else {

                if(work(1,q[1])) break;

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}