题目分析

题目大意： 在一个 N×M 的网格迷宫中，有两个角色：

• 小A（起点 'C'）：每次移动 1 格，方向为 8 个方向（上下左右+对角线）。
• 小B（起点 'D'）：每次移动 2 格，方向为 4 个方向（上下左右）。

我们需要找到一个网格点，使得两人都能到达，且两人到达该点所需的时间（回合数）的最大值最小。如果无法相遇，输出 "NO"。

这就求网格图上的最短路问题，由于边权固定（每一步代价固定），首选 BFS（广度优先搜索）。

但是因为两人的移动规则不同，我们不能简单地双向奔赴搜索，而是采用 "分别求全图距离" 的策略：

第一遍 BFS (小A)：。从 'C' 出发，使用 8 方向数组，计算小A到达地图上每一个格子 (i,j) 所需的最少步数，记为 distA[i][j]。

第二遍 BFS (小B)。 从 'D' 出发，使用 4 方向数组，计算小B到达地图上每一个格子 (i,j) 所需的最少步数（注意这里先算距离），记为 distB[i][j]。

接下来枚举相遇点计算时间。遍历地图上的每一个点 (i,j)：如果该点是障碍物或者某人无法到达，跳过。小A的时间：TA​=distA[i][j]（因为速度是 1）。小B的时间：由于小B一回合走 2 格，如果距离是 1，耗时 1；距离是 2，耗时 1；距离是 3，耗时 2。 公式为：TB​=⌈distB[i][j]/2⌉=(distB[i][j]+1)/2（利用整数除法向下取整的特性）。两人必须都到达才能算相遇，所以当前点汇合时间取决于慢的那个人：Tmeet​=max(TA​,TB​)。

最后在所有合法的汇合点中，取 Tmeet​ 的最小值即为答案。时间复杂度为O(N×M)，空间复杂度为O(N×M)。

注意

• A与B的方向数组不同。A 是 8 方向，B 是 4 方向，写 BFS 时要分开处理。
• 处理B 的速度时不要在 BFS 过程中直接让 B 跳两格（处理障碍物会很麻烦），而是按走一步算距离，最后在计算时间时除以 2。这样可以正确处理"第一步能不能走"和"第二步能不能走"的逻辑。
• 相遇逻辑不是相加除以 2，而是取最大值 max，因为先到的人可以在原地等后到的人。

AC代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

int N, M;
char a[1005][1005]; 
int dx[8]={0,1,1,1,0,-1,-1,-1}, dy[8]={1,1,0,-1,-1,-1,0,1};
struct Node {
    int x, y;
};
int dist[1005][1005]; 
int bfs(int sx, int sy)
{
    memset(dist, -1, sizeof dist);
    queue<Node> q;
    q.push({sx, sy});
    dist[sx][sy]=0;
    while(!q.empty()) {
        Node curr=q.front();
        q.pop();
        int x=curr.x;
        int y=curr.y;
        if(a[x][y]=='D') {
            return dist[x][y];
        }
        for(int i=0; i<8; i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
                if(a[nx][ny] != '#' && dist[nx][ny]==-1) {
                    dist[nx][ny]=dist[x][y]+1;
                    q.push({nx, ny});
                }
            }
        }
    }
    return -1;
}

int main()
{
    int sx, sy, ex, ey;
    cin>>N>>M;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++){
            cin>>a[i][j];
            if(a[i][j]=='C'){
                sx=i, sy=j;
            }
            if(a[i][j]=='D'){
                ex=i, ey=j;
            }
        }
    }
    int ans=bfs(sx, sy)/2;
    if(ans>=0)
    {
        cout<<"YES\n"<<ans;
    }
    else cout<<"NO";
    return 0;
}