题意

给定一个迷宫，迷宫中 A 可以向 8 个方向移动（八联通的 8 个方向），B 可以向 4 个方向移动（四联通的 4 个方向），但一单位时间可以移动两次。不能通过障碍物。问 A 和 B 是否能相遇、最早什么时候相遇。

题解

一开始理解错意思了，以为相遇必须是在某一时刻到达同一个格子。于是开始纠结 B 的“走两步”算一个还是半个时刻。

后来发现想多了，只要 A 和 B 都到达过某个格子就行了。那么直接上双向 BFS 即可。

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int n, m;
int ax, ay, bx, by;
char o[3], mat[1005][1005];
queue<int> qx1, qx2, qy1, qy2;
bool vis1[1005][1005] = {0}, vis2[1005][1005];
void init(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            scanf("%s", o);
            mat[i][j] = o[0];
            if (o[0] == 'C') ax = i, ay = j;
            if (o[0] == 'D') bx = i, by = j;
        }
    }
}
bool stepa(){
    int siz1 = qx1.size();
    while (siz1--){
        int x = qx1.front(), y = qy1.front();
        qx1.pop(), qy1.pop();
        for (int i = 0; i < 8; ++i){
            int cx = x + ddx[i], cy = y + ddy[i];
            if (cx <= 0 || cy <= 0 || cx > n || cy > m)
                continue;
            if (mat[cx][cy] == '#' || vis1[cx][cy]) continue;
            vis1[cx][cy] = true;
            if (vis2[cx][cy]) return true;
            qx1.push(cx), qy1.push(cy); 
        }
    }
    return false;
}
bool stepb(){
    int siz2 = qx2.size();
    while (siz2--){
        int x = qx2.front(), y = qy2.front();
        qx2.pop(), qy2.pop();
        for (int i = 0; i < 4; ++i){
            int cx = x + dx[i], cy = y + dy[i];
            if (cx <= 0 || cy <= 0 || cx > n || cy > m)
                continue;
            if (mat[cx][cy] == '#' || vis2[cx][cy]) continue;
            vis2[cx][cy] = true;
            if (vis1[cx][cy]) return true;
            qx2.push(cx), qy2.push(cy); 
        }
    }
    return false;
}
bool step(){
    if (stepa()) return true;
    if (stepb()) return true;
    if (stepb()) return true;
    return false;
}
void solve(){
    vis1[ax][ay] = true;
    vis2[bx][by] = true;
    qx1.push(ax), qy1.push(ay);
    qx2.push(bx), qy2.push(by);
    int ans = 0x3f3f3f3f;
    for (int st = 1; ; ++st){
        if (qx1.empty() && qx2.empty()){
            printf("NO\n");
            return ;
        }
        if (step()){
            printf("YES\n%d\n", st);
            return ;
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}