题面

考虑双向广搜。

我们需要记录男孩和女孩的当前位置，并且每次都进行扩展。

记录一个数组 \(st[i][j]\) 。

• 如果 \(st[i][j]=0\) ，说明 \((i,j)\) 还没有被男孩和女孩经过；
• 如果 \(st[i][j]=1\) ，说明 \((i,j)\) 被男孩经过了；
• 如果 \(st[i][j]=2\) ，说明 \((i,j)\) 被女孩经过了。

如果当前扩展的是男孩，且当前的位置是 \((x,y)\) ，那么当 \(st[x][y]=2\) 时直接返回当前扩展的层数即可；

如果当前扩展的是女孩，那么当 \(st[x][y]=1\) 时直接返回就可以了。

题目中有一句话：

在第 \(k\) 秒后所有与鬼的曼哈顿距离不超过 \(2k\) 的位置都会被鬼占领。

我们根据这句话的提示判断该点是否要扩展即可。

其实双队列来实现双向广搜还是比较易懂的。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 803;

int t, n, m;
char s[maxn][maxn];
int st[maxn][maxn];
pair <int, int> boy, girl, ghost[5];

const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

inline bool check(int x, int y, int step)
{
    if (x <= 0 || x > n || y <= 0 || y > n || s[x][y] == 'X') return false; //出界了或者走到了墙
    for (int i = 1; i <= 2; i+=1) 
        if (abs(x - ghost[i].first) + abs(y - ghost[i].second) <= step * 2) return false; //判断与鬼的曼哈顿距离
    return true;
}

inline int bfs()
{
    memset(st, 0, sizeof(st)); //记得数组初始化
    queue <pair <int, int> > qb, qg;
    int tot = 0;
    for (int i = 1; i <= n; i+=1)
    {
        for (int j = 1; j <= m; j+=1)
        {
            if (s[i][j] == 'M') boy = (make_pair)(i, j);
            else if (s[i][j] == 'G') girl = (make_pair)(i, j);
            else if (s[i][j] == 'Z') ghost[++tot] = (make_pair)(i, j);
            //记录男孩、女孩和鬼的位置
        }
    }
    qb.push(boy); qg.push(girl);
    int step = 0; //扩展的层数
    while (qb.size() || qg.size()) //如果还可以扩展
    {
        ++step;
        for (int i = 1; i <= 3; i+=1) //男孩扩展 3 步
        {
            for (int j = 1, len = qb.size(); j <= len; j+=1) //要对队列中的每一个元素进行扩展
            {
                pair <int, int> p = qb.front(); qb.pop();
                int x = p.first, y = p.second;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k+=1)
                {
                    int xx = x + dx[k], yy = y + dy[k];
                    if (!check(xx, yy, step)) continue;
                    if (st[xx][yy] == 2) return step;
                    if (!st[xx][yy]) 
                        st[xx][yy] = 1, qb.push((make_pair)(xx, yy));
                }
            }
        }
        for (int i = 1; i <= 1; i+=1) //女孩只要扩展一步
        {
            for (int j = 1, len = qg.size(); j <= len; j+=1)
            {
                pair <int, int> p = qg.front(); qg.pop();
                int x = p.first, y = p.second;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k+=1)
                {
                    int xx = x + dx[k], yy = y + dy[k];
                    if (!check(xx, yy, step)) continue;
                    if (st[xx][yy] == 1) return step;
                    if (!st[xx][yy]) 
                        st[xx][yy] = 2, qg.push((make_pair)(xx, yy));
                }
            }
        }
    }
    return -1; //无解
}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    t = gi();
    while (t--)
    {
        n = gi(), m = gi();
        for (int i = 1; i <= n; i+=1) scanf("%s", s[i] + 1);
        printf("%d\n", bfs());
    }
    return 0;
}

题解【AcWing177】噩梦