AcWing-177-噩梦

问题

给定一张 N×M 的地图，地图中有 1 个男孩，1 个女孩和 2 个鬼。

字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。

男孩每秒可以移动 3 个单位距离，女孩每秒可以移动 1 个单位距离，男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张 2 个单位距离，并且无视墙的阻挡，也就是在第 k 秒后所有与鬼的曼哈顿距离不超过 2k 的位置都会被鬼占领。

注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。

求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。

输入格式

第一行包含整数 T，表示共有 T 组测试用例。

每组测试用例第一行包含两个整数 N 和 M，表示地图的尺寸。

接下来 N 行每行 M 个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有 1 个男孩，1 个女孩和 2 个鬼）

输出格式

每个测试用例输出一个整数 S，表示最短会合时间。

如果无法会合则输出 −1。

每个结果占一行。

数据范围

1<n,m<800

输入样例：

3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X

输出样例：

1
1
-1

思路

• 广搜变形(双重bfs)

建立两个队列，分别存放男孩和女孩当前可能到达的位置状态。每一秒，先执行三次 bfs 对男孩的位置做扩展，在扩展过程中标记好已访问的位置（记录在 v1 数组中），再对女孩执行一次 bfs ，扩展位置，也记录好访问过的位置（记录在数组v2中），若在扩展女孩的位置时，发现当前到达的新状态男孩已经到达了，则退出循环，输出当前的时间。而对于每个bfs，从队列里取出状态后，要判断当前状态位置是否别鬼扩展的区域所占领才能使用。

题解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;
const int MAX = 805;
char s[MAX][MAX];
typedef pair<int, int> PII;
int t, n, m;
bool v1[MAX][MAX], v2[MAX][MAX];
PII ghost[2];
queue<PII> q1, q2;
int dir[4][2] = {{0,  1},
                 {1,  0},
                 {0,  -1},
                 {-1, 0}};

void bfs1(int k) {
    int size = q1.size();
    for (int i = 0; i < size; i++) {
        auto now = q1.front();
        q1.pop();
        if (abs(now.first - ghost[0].first) + abs(now.second - ghost[0].second) <= 2 * k) continue;
        if (abs(now.first - ghost[1].first) + abs(now.second - ghost[1].second) <= 2 * k) continue;

        for (int i = 0; i < 4; ++i) {
            int ti = now.first + dir[i][0], tj = now.second + dir[i][1];
            if (ti < 0 || ti >= n || tj < 0 || tj >= m) continue;
            if (s[ti][tj] == 'X') continue;
            if (v1[ti][tj]) continue;
            if (abs(ti - ghost[0].first) + abs(tj - ghost[0].second) <= 2 * k) continue;
            if (abs(ti - ghost[1].first) + abs(tj - ghost[1].second) <= 2 * k) continue;

            q1.push({ti, tj});
            v1[ti][tj] = true;    //第三步才记录时间
        }
    }
}

bool bfs2(int k) {
    int size = q2.size();
    for (int i = 0; i < size; i++) {
        auto now = q2.front();
        q2.pop();
        if (abs(now.first - ghost[0].first) + abs(now.second - ghost[0].second) <= 2 * k) continue;
        if (abs(now.first - ghost[1].first) + abs(now.second - ghost[1].second) <= 2 * k) continue;

        for (int i = 0; i < 4; ++i) {
            int ti = now.first + dir[i][0], tj = now.second + dir[i][1];
            if (ti < 0 || ti >= n || tj < 0 || tj >= m) continue;
            if (s[ti][tj] == 'X') continue;
            if (v2[ti][tj]) continue;
            if (abs(ti - ghost[0].first) + abs(tj - ghost[0].second) <= 2 * k) continue;
            if (abs(ti - ghost[1].first) + abs(tj - ghost[1].second) <= 2 * k) continue;

            if (v1[ti][tj]) return true;
            v2[ti][tj] = true;
            q2.push({ti, tj});
        }
    }
    return false;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        while (q1.size()) q1.pop();
        while (q2.size()) q2.pop();

        memset(v1, 0, sizeof(v1));
        memset(v2, 0, sizeof(v2));
        int cnt_ghost = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%s", s[i]);
            for (int j = 0; j < m; ++j) {
                if (s[i][j] == 'M') {
                    q1.push({i, j});
                    v1[i][j] = true;
                } else if (s[i][j] == 'G') {
                    q2.push({i, j});
                    v2[i][j] = true;
                } else if (s[i][j] == 'Z') ghost[cnt_ghost++] = {i, j};
            }
        }

        bool st = false;
        int ans = 0;
        while (q1.size() && q2.size()) {
            ans++;
            for (int i = 0; i < 3; i++) bfs1(ans);
            if (bfs2(ans)) {
                cout << ans << endl;
                st = true;
                break;
            }
        }
        if (!st) cout << -1 << endl;
    }

    return 0;
}