信息学奥赛一本通T1450：Knight Moves

【题目描述】

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

【输入】

第一行给出骑士的数量 n。

在接下来的 3n 行中，每 3 行描述了一个骑士。其中，第一行一个整数 L 表示棋盘的大小，整个棋盘大小为 L×L；

第二行和第三行分别包含一对整数 (x,y)，表示骑士的起始点和终点。假设对于每一个骑士，起始点和终点均合理。

【输出】

对每一个骑士，输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同，则输出 0

【输入样例】

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

【输出样例】

5
28
0

思路：

BFS 板子题，与 Knight Moves（信息学奥赛一本通-T1257）一个题

下面给出一种 BFS 的优化做法，可以极大加快搜索速度，即：双向BFS

设置两个队列 posQ 和 negQ，分别代表从起点开始搜索的队列和从终点开始搜索的队列

对于判重数组 vis[i][j]，我们设置三个状态：未被访问时为 0，正向搜索到时设为 1，逆向搜索到时设为 2

这样一来，当正向搜索到 vis[i][j]=2 或逆向搜索到 vis[i][j]=1 时，说明终点起点相遇，此时记录两者步数输出即可

此时的步数即为相遇时起点到该点的距离 dis[nx][ny]+dis[x][y]+1

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; }
LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;}
LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;}
LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; }
LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); }
LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
const double EPS = 1E-6;
const int MOD = 1000000000+7;
const int N = 1000+5;
const int dnewStr[] = {0,0,-1,1,1,-1,1,1};
const int dy[] = {1,-1,0,0,-1,1,-1,1};
using namespace std;

struct Node {
    int x, y;
    Node() {}
    Node(int x, int y) : x(x), y(y) {}
};
int n;
int vis[N][N];
int dis[N][N];
int dir[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};
void BFS(Node st, Node ed) {
    if (st.x == ed.x && st.y == ed.y) {
        printf("0\n");
        return;
    }

    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<Node> posQ; //正向队列
    queue<Node> negQ; //反向队列

    posQ.push(st);
    negQ.push(ed);
    vis[st.x][st.y] = 1;
    vis[ed.x][ed.y] = 2;
    while (!posQ.empty() || !negQ.empty()) {
        if (!posQ.empty()) {
            Node now = posQ.front();
            posQ.pop();
            int x = now.x;
            int y = now.y;

            for (int i = 0; i < 8; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if (vis[nx][ny] == 2) { //相遇
                    int step = dis[x][y] + dis[nx][ny] + 1;
                    printf("%d\n", step);
                    return;
                } 
                if (vis[nx][ny] == 0) {
                    vis[nx][ny] = 1;
                    dis[nx][ny] = dis[x][y] + 1;
                    posQ.push(Node(nx, ny));
                }
            }
        }
        if (!negQ.empty()) {
            Node now = negQ.front();
            int x = now.x;
            int y = now.y;

            for (int i = 0; i < 8; i++) {
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if (vis[nx][ny] == 1) { //相遇
                    int step = dis[nx][ny] + dis[x][y] + 1;
                    printf("%d\n", step);
                    return;
                } 
                if (vis[nx][ny] == 0) {
                    vis[nx][ny] = 2;
                    dis[nx][ny] = dis[x][y] + 1;
                    negQ.push(Node(nx, ny));
                }
            }
        }
    }
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        Node st, ed;
        scanf("%d%d%d%d", &st.x, &st.y, &ed.x, &ed.y);
        BFS(st, ed);
    }
    return 0;
}

信息学奥赛一本通T1450：深搜的剪枝技巧 Knight Moves 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 Knight Moves