侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【BFS】噩梦

GabrielxD
2022-12-30 / 0 评论 / 0 点赞 / 316 阅读 / 1,312 字
温馨提示:
本文最后更新于 2022-12-30,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

177. 噩梦 - AcWing题库


给定一张 N×MN \times M 的地图,地图中有 11 个男孩, 11 个女孩和 22 个鬼。

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

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

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

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

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

输入格式

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

每组测试用例第一行包含两个整数 NNMM ,表示地图的尺寸。

接下来 NN 行每行 MM 个字符,用来描绘整张地图的状况。(注意:地图中一定有且仅有 11 个男孩, 11 个女孩和 22 个鬼)

输出格式

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

如果无法会合则输出 1-1

每个结果占一行。

数据范围

1<n,m<8001 < 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模板题,但本题的设计比较复杂,有几个细节需要注意:

  • 鬼('Z')每秒行动的范围是( 'z' ):

      z  
     zzz
    zzZzz
     zzz
      z
    
  • 鬼无视墙的阻挡:直接理解成鬼能往墙上走就行了(反正鬼和墙都能挡人)。

  • 男孩每秒可以移动 33 个单位距离不是指只能向上下左右其中一个方向移动 33 个单位,而是指男孩每轮可以进行 33 次距离为 11 的移动。

代码

#include <iostream>
#include <limits>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 810;
// ⬇️⬆️➡️⬅️
const int DIRS4[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// ↖️⬆️↗️⬅️➡️↙️⬇️↘️
const int DIRS8[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int t, n, m;
char g[N][N];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        queue<PII> oni_que, boy_que, girl_que;
        for (int i = 0; i < n; ++i) {
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            for (int j = 0; j < m; ++j) {
                char c;
                scanf("%c", &c);
                if (c == 'Z') oni_que.push({i ,j});
                else if (c == 'M') boy_que.push({i, j});
                else if (c == 'G') girl_que.push({i, j});
                g[i][j] = c;
            }
        }
        int step = 0; // 时间(轮数)
        while (!oni_que.empty() && !boy_que.empty() && !girl_que.empty()) {
            ++step;
            int sz = oni_que.size();
            // 鬼行动
            while (sz--) {
                auto pr = oni_que.front();
                oni_que.pop();
                int x = pr.first, y = pr.second;
                for (auto& DIR : DIRS8) {
                    int nx = x + DIR[0], ny = y + DIR[1];
                    // 不能越界 不能走之前走过的地方(剪枝)
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 'Z') {
                        g[nx][ny] = 'Z';
                        oni_que.push({nx, ny});
                    }
                }
                for (auto& DIR : DIRS4) {
                    int nx = x + DIR[0] * 2, ny = y + DIR[1] * 2;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 'Z') {
                        g[nx][ny] = 'Z';
                        oni_que.push({nx, ny});
                    }
                }
            }
            // 男孩行动三次
            for (int k = 0; k < 3; ++k) {
                sz = boy_que.size();
                while (sz--) {
                    auto pr = boy_que.front();
                    boy_que.pop();
                    int x = pr.first, y = pr.second;
                    if (g[x][y] == 'Z') continue;
                    for (auto& DIR : DIRS4) {
                        int nx = x + DIR[0], ny = y + DIR[1];
                        // 不能越界 不能走鬼或者墙上 不能走之前走过的地方(剪枝)
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m ||
                            g[nx][ny] == 'X' || g[nx][ny] == 'Z' || g[nx][ny] == 'M') continue;
                        // 如果遇到女孩 直接输出当前轮次 结束
                        if (g[nx][ny] == 'G') {
                            printf("%d\n", step);
                            goto out;
                        }
                        g[nx][ny] = 'M';
                        boy_que.push({nx, ny});
                    }
                }
            }
            sz = girl_que.size();
            // 女孩行动一次
            while (sz--) {
                auto pr = girl_que.front();
                girl_que.pop();
                int x = pr.first, y = pr.second;
                if (g[x][y] == 'Z') continue;
                for (auto& DIR : DIRS4) {
                    int nx = x + DIR[0], ny = y + DIR[1];
                    // 不能越界 不能走鬼或者墙上 不能走之前走过的地方(剪枝)
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m ||
                        g[nx][ny] == 'X' || g[nx][ny] == 'Z' || g[nx][ny] == 'G') continue;
                    // 如果遇到男孩 直接输出当前轮次 结束
                    if (g[nx][ny] == 'M') {
                        printf("%d\n", step);
                        goto out;
                    }
                    g[nx][ny] = 'G';
                    girl_que.push({nx, ny});
                }
            }
        }
        // 遇不到 输出-1 结束
        puts("-1");
        out:;
    }
    
    return 0;
}   
0

评论区