【例65.2】 清除地雷

解题思路

用队列扩散引爆。仅原来为1且未引爆的地雷会入队；出队后把自身和八邻域输出标为2，其中遇到原地雷继续入队。原图与结果图分开保存。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

土地也会被炸成2，但不能继续传播；起点为0时原样输出。

复杂度

时间O(nm)，空间O(nm)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &s : a)
        cin >> s;
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    auto b = a;
    vector<vector<bool>> seen(n, vector<bool>(m));
    queue<pair<int, int>> q;
    if (a[x][y] == '1') {
        q.push({x, y});
        seen[x][y] = true;
    }
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++) {
                int i = p.first + dx, j = p.second + dy;
                if (i < 0 || i >= n || j < 0 || j >= m)
                    continue;
                b[i][j] = '2';
                if (a[i][j] == '1' && !seen[i][j]) {
                    seen[i][j] = true;
                    q.push({i, j});
                }
            }
    }
    for (auto &s : b)
        cout << s << "\n";
    return 0;
}