D. Solve The Maze - 题解

比赛与标签

比赛: Codeforces Round 648 (Div. 2) 标签: constructive algorithms, dfs and similar, dsu, graphs, greedy, implementation, shortest paths 难度: *1700

题目大意喵~

我们有一个 n x m 大小的迷宫，里面有四种东西：

.：空地
#：墙壁
G：好人
B：坏人

迷宫的出口在右下角的 (n, m) 位置。人可以在相邻（上下左右）的非墙壁格子里移动。

我们的任务是，判断是否可以通过把一些（零个或多个）空地 . 变成墙壁 #，来满足下面两个条件：

所有好人 G 都能成功走到出口。
所有坏人 B 都不能走到出口。

需要注意的是，原来是 G 或 B 的格子是不能被我们改成墙壁的哦。题目保证了出口 (n, m) 最初一定是空地 .。

解题思路分析呐！

这道题问的是“是否存在”一种方案，而不是让我们找出最优方案。这种时候，我们通常可以大胆地去想一个最简单、最直接的策略，看看它能不能行得通，这也就是所谓的构造性思维和贪心策略啦！

我们的目标很明确：让好人 G 通行，让坏人 B 寸步难行。

如何对付坏人 B 呢？ 最狠的办法，当然是把他们全都关起来！只要一个 B 的四周都是墙壁，他就哪里也去不了，自然也到不了出口啦。所以，一个非常贪心的想法就诞生了：我们把所有 B 周围的空地 . 全都变成墙壁 #！

这样一来，我们就尽了最大的努力去封堵坏人 B。但是，这么做会不会有什么问题呢？

坏人 B 旁边是好人 G：如果一个 B 的旁边紧挨着一个 G，我们就没办法在他们之间砌墙了。那么这个 B 就可以移动到 G 的位置。如果这个 G 能到出口，那这个 B 也就一定能到出口。这就直接违反了我们的第二个条件！所以，只要有任何一个 B 和 G 相邻，就一定无解，可以直接输出 "No" 啦，喵~
封堵 B 的时候，会不会把 G 的路也堵死了？ 这是完全有可能的！我们把 B 旁边的 . 都变成 # 之后，可能会形成新的墙壁，恰好把某个 G 通往出口的路给切断了。

所以，我们的完整策略就清晰起来了：

第一步：预处理与封堵 遍历整个迷宫。找到每一个坏人 B。检查它的上下左右四个邻居：

如果邻居是好人 G，说明神仙也救不了了，直接判定为 "No"。
如果邻居是空地 .，就毫不犹豫地把它变成墙壁 #。这是我们能做的最强的封堵了。
如果邻居是墙壁 # 或者另一个坏人 B，那我们什么也不用做。

第二步：验证可行性 经过第一步，我们得到了一个“改造后”的迷宫。在这个迷宫里，我们已经尽力把所有 B 都关起来了。现在，我们需要验证两个最终条件：

所有 G 都能到达出口 (n-1, m-1) 吗？
所有 B 都不能到达出口 (n-1, m-1) 吗？

这是一个经典的可达性问题，用 BFS (广度优先搜索) 或 DFS (深度优先搜索) 就能轻松解决！一个很巧妙的做法是，我们从出口 (n-1, m-1) 开始进行一次 BFS，看看它能到达哪些格子。

我们从 (n-1, m-1) 出发（前提是它没在第一步被我们堵上），把所有能走到的非墙壁格子都标记为“可达”。
BFS 结束后，我们再遍历一遍整个迷宫：
- 如果发现某个好人 G 所在的格子是“不可达”的，说明他被困住了，输出 "No"。
- 如果发现某个坏人 B 所在的格子是“可达”的，说明我们的封堵失败了，他也溜出来了，输出 "No"。

如果以上所有检查都通过了，那就说明我们成功找到了一个可行的方案！输出 "Yes" 就好啦！(≧∇≦)ﾉ

总结一下就是：先贪心地堵住所有 B，然后用一次 BFS 检查这个方案是否满足所有 G 和 B 的最终要求。是不是很简单明了的说？

代码实现喵~

下面就是一份清晰的AC代码，本猫娘已经加上了详细的注释，方便大家理解每一部分的逻辑哦！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <queue>

// Function to solve a single test case
void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    // 定义上下左右四个方向的移动，喵~
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    
    // 一个好用的小帮手函数，判断坐标是否在迷宫内
    auto is_valid = [&](int r, int c) {
        return r >= 0 && r < n && c >= 0 && c < m;
    };

    // Step 1: 贪心策略！把所有坏人'B'旁边的空地'.'都变成墙'#'
    // 如果坏人旁边就是好人'G'，那直接就无解了喵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 'B') {
                for (int k = 0; k < 4; ++k) {
                    int ni = i + dr[k];
                    int nj = j + dc[k];
                    if (is_valid(ni, nj)) {
                        if (grid[ni][nj] == 'G') {
                            std::cout << "No\n";
                            return;
                        }
                        if (grid[ni][nj] == '.') {
                            grid[ni][nj] = '#';
                        }
                    }
                }
            }
        }
    }

    // Step 2: 从出口(n-1, m-1)开始做BFS，看看哪些格子可以到达出口
    std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));
    std::queue<std::pair<int, int>> q;

    // 出口(n-1, m-1)必须是可通行的才能开始BFS
    // 注意，它可能在第一步被我们堵住了哦！
    if (grid[n - 1][m - 1] != '#') {
        q.push({n - 1, m - 1});
        visited[n - 1][m - 1] = true;
    }

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            // 只要是合法的、没访问过的、不是墙的格子，都可以继续探索
            if (is_valid(nr, nc) && !visited[nr][nc] && grid[nr][nc] != '#') {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }

    // Step 3: 最终检查！所有好人'G'都必须能到达出口，所有坏人'B'都不能
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 如果一个好人没被访问到，说明他被困住了
            if (grid[i][j] == 'G' && !visited[i][j]) {
                std::cout << "No\n";
                return;
            }
            // 如果一个坏人被访问到了，说明他溜出来了
            if (grid[i][j] == 'B' && visited[i][j]) {
                std::cout << "No\n";
                return;
            }
        }
    }

    // 所有检查都通过了，太棒了！存在这样的方案！
    std::cout << "Yes\n";
}

int main() {
    // 加速输入输出，是个好习惯喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N * M) 的说。整个过程我们把迷宫遍历了常数次。第一次是封堵坏人，第二次是BFS，第三次是最终检查。每次遍历都是 O(N * M) 的时间，所以总时间复杂度就是 O(N * M) 啦，非常高效！
空间复杂度: O(N * M) 的说。我们主要用了 grid 数组来存储迷宫，visited 数组来记录BFS状态，还有BFS的队列 q。它们占用的空间都和迷宫的大小成正比，所以空间复杂度是 O(N * M)。

知识点与总结

这道题真是一次有趣的思维锻炼呢！让本猫娘来总结一下我们学到了什么吧：

贪心与构造思想: 面对“是否存在”这类问题，可以尝试构造一个最极端或最简单的方案，然后验证其可行性。本题的贪心点在于“最大程度地封锁坏人”。
逆向思维: 从终点开始BFS/DFS是一个非常有用的技巧！它能一次性找出所有能到达终点的格子，比从多个起点（比如所有'G'）出发要简洁得多。
图论建模: 迷宫问题本质上就是图论问题。每个格子是图的一个节点，相邻的非墙壁格子之间有边。BFS/DFS是解决图上可达性问题的标准武器。
边界情况处理: 要特别注意处理一些特殊情况，比如坏人 B 和好人 G 相邻，或者出口 (n, m) 本身就被我们封锁了。细心才能不出错哦！

好啦，今天的题解就到这里啦！希望大家都能理解并掌握这种解决问题的思路。继续努力，下一道题也一定能轻松解决的，喵~ (ฅ^•ﻌ•^ฅ)

D. Solve The Maze - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析呐！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​