P4961 小埋与扫雷

题目背景

小埋总是在家中打游戏，一天，她突然想玩Windows自带的扫雷，在一旁的哥哥看见了，想起了自己小时候信息课在机房玩扫雷的日子，便兴致勃勃地开始教小埋扫雷。然而，小埋还是不明白 \(\mathrm{3bv}\)（Bechtel's Board Benchmark Value，每局将所有非雷的方块点开所需最少左键点击数，参见扫雷网的教程 ）怎么算，于是她找到了你。

题目描述

小埋会告诉你一盘扫雷，用一个 \(n\times m\) 的矩阵表示，\(1\) 是雷 ，\(0\) 不是雷，请你告诉她这盘扫雷的 \(\mathrm{3bv}\) 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。$\mathrm{3bv}=\ \(周围八格没有“空格”的“数字”个数\)+$“空"的个数。

如果看不懂上面的计算方式，可以看题目背景中给出的教程，或者看下面的样例解释。

注：八连通

输入格式

第一行有两个整数 \(n\) 和 \(m\)，代表这盘扫雷是一个 \(n \times m\) 的矩阵。

后面的 \(n\) 行每行有 \(m\) 个整数，表示这个矩阵，每个数字为 \(0\) 或 \(1\)，\(1\) 代表是雷，\(0\) 代表不是雷。

输出格式

一个整数，代表这盘扫雷的 \(\mathrm{3bv}\) 。

输入输出样例 #1

输入 #1

8 8
0 0 0 1 1 0 0 0 
1 0 0 1 0 0 0 1 
1 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 

输出 #1

13

说明/提示

\(1\le n,\ m\le 1000\)

样例解释

Tip

找不到这道题的解题视频，
但是这道题我个人推测期末不会考，如果一定要掌握建议去看这个最基础的扫雷题目
b站讲解链接

📌 题目分析

给定数据：

一个 n × m 的矩阵 (1 ≤ n, m ≤ 1000)
1 代表地雷，0 代表安全区域

要求计算这盘扫雷的 \(\mathrm{3bv}\) 值。 根据题意：\(\mathrm{3bv} = (\text{周围八格没有“空格”的“数字”个数}) + (\text{“空”的连通块个数})\)。

👉 本质：

图的遍历（八连通块的 Flood Fill）与网格邻域判定

👉 类型：

广度优先搜索 (BFS) / 模拟

🧠 解题思路

1️⃣ 概念拆解与预处理

题目中对两个名词给出了严谨的定义，我们需要在代码中将它们量化： * “空格”：自身不是雷，且周围 8 个方向的地雷总数为 0。 * “数字”：自身不是雷，且周围 8 个方向的地雷总数 \(>0\)。

因此，第一步我们需要遍历整个矩阵。对于每一个非雷的格子，统计它 8 个方向上的地雷总数，存入一个新的二维数组 val 中。 * val[x][y] == 0 代表它是“空格”。 * val[x][y] > 0 代表它是“数字”。 * val[x][y] == -1（或不处理）代表它是雷。

2️⃣ 搜索八连通的“空”

题目的前半段要求找“由‘空格’组成的八连通块”。 我们在网格中寻找所有 val == 0 且尚未被访问过的格子，每找到一个，说明发现了一个新的“空”区块，答案加一。 随即启动一次 BFS（广度优先搜索），向 8 个方向蔓延，把与它相连的所有“空格”全部标记为已访问，避免重复计算。

3️⃣ 寻找孤立的“数字”

题目的后半段要求找“周围八格没有‘空格’的‘数字’”。 我们再次遍历网格，只关注那些 val > 0 的“数字”格子。对于每个这样的格子，去检查它周围的 8 个邻居： * 如果 8 个邻居中存在至少一个 val == 0 的“空格”，说明它在游戏里会随着那个“空”一起被自动点开，不需要我们手动点击。 * 如果 8 个邻居中全都不等于 0，说明这是一个“孤立的数字”，必须手动点开，答案加一。

4️⃣ 时间复杂度

预处理邻域：遍历每个格子，每个格子看 8 个方向，操作次数大约是 \(8 \times N \times M\)。 BFS 找连通块：每个 0 格子最多被入队出队一次，操作次数上限也是 \(8 \times N \times M\)。 找孤立数字：遍历所有大于 0 的格子看 8 个方向，同理。 总时间复杂度：\(O(N \times M)\)。 当 \(N, M \le 1000\) 时，总计算量在 \(3 \times 10^7\) 左右，在 C++ 1 秒的时限内完全可以轻松跑完。

---

💻 C++代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
int mine[1005][1005];
int val[1005][1005];  // 记录周围地雷数，-1 表示雷本身
bool vis[1005][1005]; // 用于 BFS 的访问标记

// 8个方向的偏移量：上、下、左、右、左上、右上、左下、右下
int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mine[i][j];
        }
    }

    // 1. 预处理：计算每个格子的 val 值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mine[i][j] == 1) {
                val[i][j] = -1; // 雷
                continue;
            }
            int count = 0;
            for (int k = 0; k < 8; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mine[nx][ny] == 1) {
                    count++;
                }
            }
            val[i][j] = count;
        }
    }

    int ans = 0;

    // 2. 计算“空”的个数（由 val == 0 组成的八连通块）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (val[i][j] == 0 && !vis[i][j]) {
                ans++; // 找到一个新的连通块

                // BFS 蔓延
                queue<pair<int, int>> q;
                q.push({i, j});
                vis[i][j] = true;

                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();

                    for (int k = 0; k < 8; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && val[nx][ny] == 0 && !vis[nx][ny]) {
                            vis[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }

    // 3. 计算周围没有“空格”的“数字”个数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (val[i][j] > 0) { // 如果是“数字”
                bool has_space = false;
                for (int k = 0; k < 8; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    // 检查是否存在“空格”
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && val[nx][ny] == 0) {
                        has_space = true;
                        break;
                    }
                }
                // 如果周围 8 格全都没有空格，必须手动点击
                if (!has_space) {
                    ans++;
                }
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

---

⚠️ 易错点

❌ 1. 递归深度导致爆栈 (RE)

最大 \(1000 \times 1000\) 的网格，如果极端情况下全是 0，使用纯粹的 DFS 递归去搜连通块，递归层数会达到惊人的 \(10^6\) 层。这在大多数评测机（默认栈大小通常只有几 MB 到十几 MB）上必定触发栈溢出 (Runtime Error)。对于大面积连通块，用 Queue 写 BFS 是最稳妥的选择。

❌ 2. 错把“雷”算作“数字”

题目的定义极其严谨：“自身不是雷”是前提条件！ 如果在计算孤立数字时，你仅仅写了 mine != 1 但忘记排查它自己本身，或者在统计邻居地雷数时把雷也标注成了大于 0 的数，就会导致答案凭空多出一大截。

❌ 3. 连通性理解偏差

在细胞或者走迷宫问题里，我们习惯了用上下左右（四连通）作为方向数组。但在这道扫雷题里，对角线上的 0 也是能够互相触发自动点开的。必须开 8 个方向的 dx 和 dy。

---

🚀 一句话总结

3bv 就是计算为了解开这盘扫雷，最少需要用鼠标左键点几下：连成一片的空地只需点 1 下，四周没空地的数字必须挨个点。

---

🔥 补充

关于 3bv 与高阶扫雷机制

你在题目里看到的 \(\mathrm{3bv}\) 其实是专业扫雷圈用来衡量一张地图“难度”和“最少点击数”的核心指标： * 在不考虑“盲猜”和“双击（Chord，即左右键同按）”的情况下，玩通一局游戏的最少左键点击次数就是 \(\mathrm{3bv}\)。 * 扫雷竞速玩家经常看的一个指标叫 \(\mathrm{3bv}/s\)。意思是“每秒能处理多少个有效 3bv 点击”。如果一个玩家的 \(\mathrm{3bv}/s\) 大于 3，基本上就是人类极限反应的高手了。 * 本质上，扫雷的引擎在玩家点击一个空白区域时，执行的正是和我们代码里一样的 BFS/Flood Fill 算法，瞬间把那些相连的“空格”以及边缘的“数字”翻开。你在这道题里手写的代码，就是还原了扫雷游戏底层的核心物理引擎！