1.前置知识

双向bfs

2.题意

已经很明了了吧。。。

3.解法

这道题要我们模拟两个人的移动，数据范围也不大，所以直接对两个人同时bfs即可。第一次相遇时即为最小时间。我喜欢每次模拟一步，至于b能移动两次就跑两次bfs就好了。

4.时间复杂度

5.代码

#include<stdio.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, ax, ay, bx, by, ans = inf;
int dxa[9] = { 0,-1,-1,0,1,1,1,0,-1 }, dya[9] = { 0,0,1,1,1,0,-1,-1,-1 };
int dxb[5] = { 0,-1,0,1,0 }, dyb[5] = { 0,0,1,0,-1 };
int mp[1005][1005][2];
struct node
{
    int x, y;
    node(int _x, int _y)
    {
        x = _x;
        y = _y;
    }
};
queue<node> q[2];
bool bfs(int type)
{
    int T = q[type].size();
    while(T--)
    {
        node x = q[type].front();
        q[type].pop();
        for (int i = 1; i <= 8-4*type; i++)
        {
            int tx = x.x, ty = x.y;
            if (type == 0)tx += dxa[i], ty += dya[i];
            else tx += dxb[i], ty += dyb[i];
            if (1 <= tx && tx <= n && 1 <= ty && ty <= m)
            {
                if (mp[tx][ty][1 - type] == 1)return true;
                if (mp[tx][ty][type] == 0)
                {
                    q[type].push(node(tx, ty));
                    mp[tx][ty][type] = 1;
                }
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d %d\n", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c;
            c = getchar();
            getchar();
            if (c == '#')mp[i][j][0] = mp[i][j][1] = -1;
            else if (c == 'C')
            {
                mp[i][j][0] = 1;
                q[0].push(node(i, j));
            }
            else if (c == 'D')
            {
                mp[i][j][1] = 1;
                q[1].push(node(i, j));
            }
        }
    for (int i = 1; !q[0].empty() || !q[1].empty(); i++)
        if (bfs(0) || bfs(1) || bfs(1))
        {
            printf("YES\n%d", i);
            return 0;
        }
    printf("NO");
    return 0;
}