零、题目描述与直观演示

题目链接：力扣 529.扫雷游戏
扫雷游戏体验链接：扫雷游戏（可实操理解规则）

题目描述：

示例1:

输入：board = [
[“E”,“E”,“E”,“E”,“E”],
[“E”,“E”,“M”,“E”,“E”],
[“E”,“E”,“E”,“E”,“E”],
[“E”,“E”,“E”,“E”,“E”] ], click = [3,0]

输出：[
[“B”,“1”,“E”,“1”,“B”],
[“B”,“1”,“M”,“1”,“B”],
[“B”,“1”,“1”,“1”,“B”],
[“B”,“B”,“B”,“B”,“B”]]

示例2:

输入：board = [
[“B”,“1”,“E”,“1”,“B”],
[“B”,“1”,“M”,“1”,“B”],
[“B”,“1”,“1”,“1”,“B”],
[“B”,“B”,“B”,“B”,“B”]], click = [1,2]

输出：[
[“B”,“1”,“E”,“1”,“B”],
[“B”,“1”,“X”,“1”,“B”],
[“B”,“1”,“1”,“1”,“B”],
[“B”,“B”,“B”,“B”,“B”]]

直观演示：扫雷棋盘的更新过程

为了更清晰理解规则，我们以示例1为例，拆解点击后的棋盘变化：

初始棋盘（未点击时）

[
     0      1     2    3     4
0 [“E”, “E”, “E”, “E”, “E”], // E：未翻开的空方块（灰色）
1 [“E”, “E”, “M”, “E”, “E”], // M：未翻开的地雷（红色）
2 [“E”, “E”, “E”, “E”, “E”],
3 [“E”, “E”, “E”, “E”, “E”]
]

点击坐标：(3,0)（第3行第0列）
按规则逐步更新如下：

步骤1：点击'E'，标记为'B'
初始点击位置为未翻开的空方块，先标记为'B'（已探索）：

     0      1     2    3     4
3 [“B”, “E”, “E”, “E”, “E”] ← (3,0) 从’E’→’B’（已探索）

步骤2：计算周围地雷数（mineCount=0）
检查(3,0)的8个方向（上、下、左、右、四斜向），均无地雷，因此需要向8个方向的'E'扩散。

步骤3：递归扩散至(2,0)并标记
(2,0)为未探索的'E'，标记为'B'后继续扩散：

     0      1     2    3     4
2 [“B”, “E”, “E”, “E”, “E”], ← (2,0) 从’E’→’B’（已探索）
3 [“B”, “E”, “E”, “E”, “E”], ← (3,0) 从’E’→’B’（已探索）

步骤4：(2,0)继续扩散至(1,0)、(2,1)、(3,1)
这三个位置均为'E'，标记为'B'后继续扩散：

     0      1     2    3     4
1 [“B”, “E”, “M”, “E”, “E”], ← (1,0) 从’E’→’B’
2 [“B”, “B”, “E”, “E”, “E”], ← (2,1) 从’E’→’B’
3 [“B”, “B”, “E”, “E”, “E”], ← (3,1) 从’E’→’B’

步骤5：(1,0)扩散至(0,1)，触发地雷检测
(0,1)计算8方向时，发现(1,2)是地雷（'M'），mineCount=1，因此从'B'改为'1'并终止扩散：

     0      1     2    3     4
0 [“B”, “1”, “E”, “E”, “E”], ← (0,1) 从’B’→’1’（周围1个地雷）

步骤6：(2,1)检测到地雷，改为'1'
(2,1)上方(1,2)是地雷，mineCount=1，改为'1'并终止扩散：

     0      1     2    3     4
2 [“B”, “1”, “E”, “E”, “E”], ← (2,1) 从’B’→’1’（周围1个地雷）

步骤7：右侧区域扩散与地雷周围标记
(3,1)向右侧扩散至(3,2)-(3,4)，最终覆盖右侧区域；同时，(1,2)周围的(1,1)、(1,3)等格子检测到地雷，均改为'1'。

最终棋盘

[
     0      1    2    3     4
0 [“B”, “1”, “E”, “1”, “B”],
1 [“B”, “1”, “M”, “1”, “B”],
2 [“B”, “1”, “1”, “1”, “B”],
3 [“B”, “B”, “B”, “B”, “B”]
]

关键变化说明：

• 'B'：已探索且周围无地雷的区域；
• 数字（如'1'）：周围地雷数量；
• 'E'：未被扩散到的未探索区域；
• 'M'：未被点击的地雷（仍保持初始状态）。

一、为什么这道题值得咱们学习？

这道题是网格类DFS的经典进阶题，核心价值在于：

1. 8方向遍历的实践：相比「岛屿数量」的4方向遍历，本题需包含对角线方向，更贴近“周围”的实际定义，是面试高频考点；
2. Flood Fill算法的延伸：通过“递归扩散+状态标记”模拟扫雷规则，强化对“洪水灌溉”思想的理解；
3. 递归逻辑的精细化控制：需根据“周围地雷数”动态决定是否终止递归，锻炼复杂条件下的逻辑设计能力。

对算法感兴趣的小伙伴可以订阅我的每日一题专栏，近期聚焦“洪水灌溉（Flood Fill）”和“DFS”系列，从基础到进阶逐步深入，适合系统性学习~

二、思路探索

核心目标：模拟扫雷点击逻辑，重点处理空方块的递归扩散。

步骤拆解：

1. 处理点击事件：判断点击位置是地雷（'M'）还是空方块（'E'）；
2. 计算周围地雷数：对空方块，遍历8个方向统计'M'的数量；
3. 扩散或终止：
   • 若地雷数>0：更新为数字字符，终止递归；
   • 若地雷数=0：标记为'B'，向8个方向的'E'递归扩散。

关键难点：8方向的边界控制（避免越界）和递归重复访问（需提前标记）。

三、代码实现

class Solution {
public:
    // 8个方向偏移量：下、上、右、左、右下、右上、左下、左上
    int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
    int dy[8] = {0, 0, 1, -1, -1, -1, 1, 1};
    int m, n;  // 网格行数和列数

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int x = click[0], y = click[1];  // 解析点击坐标
        m = board.size();                // 初始化行数
        n = board[0].size();             // 初始化列数

        // 情况1：点击到地雷（'M'），标记为'X'并返回
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }

        // 情况2：点击到空方块（'E'），标记为'B'后启动DFS
        board[x][y] = 'B';
        dfs(board, x, y);

        return board;
    }

    // DFS：处理空方块的扩散逻辑
    void dfs(vector<vector<char>>& board, int x, int y) {
        // 步骤1：计算周围8方向的地雷数量
        int mineCount = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];  // 新行坐标
            int ny = y + dy[i];  // 新列坐标
            // 边界检查 + 统计地雷
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'M') {
                mineCount++;
            }
        }

        // 步骤2：根据地雷数量决定是否扩散
        if (mineCount > 0) {
            // 周围有地雷，更新为数字字符并终止递归
            board[x][y] = mineCount + '0';
            return;
        } else {
            // 周围无地雷，向8方向的'E'扩散
            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 边界检查 + 未探索的空方块（'E'）
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'E') {
                    board[nx][ny] = 'B';  // 提前标记为已探索，避免重复递归
                    dfs(board, nx, ny);   // 递归扩散
                }
            }
        }
    }
};

代码细节拆解

1. 8方向偏移量数组

int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};  // 行偏移
int dy[8] = {0, 0, 1, -1, -1, -1, 1, 1};  // 列偏移

8方向偏移对应关系：
dx[i] | dy[i] | 方向
1     | 0     | 向下（x+1, y）
-1    | 0     | 向上（x-1, y）
0     | 1     | 向右（x, y+1）
0     | -1    | 向左（x, y-1）
1     | -1    | 右下（x+1, y-1）
-1    | -1    | 右上（x-1, y-1）
1     | 1     | 左下（x+1, y+1）
-1    | 1     | 左上（x-1, y+1）

• 作用：定义从(x,y)向8个方向移动的坐标变化。例如：
  • i=0：(x+1, y)（向下）；i=4：(x+1, y-1)（右下）。
• 与4方向的区别：相比“岛屿数量”等题目，新增4个对角线方向，更贴合“周围”的实际定义。

2. 主函数updateBoard解析

vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
    int x = click[0], y = click[1];
    m = board.size(); n = board[0].size();

    if (board[x][y] == 'M') {  // 点击地雷
        board[x][y] = 'X';
        return board;
    }

    board[x][y] = 'B';  // 标记空方块为已探索
    dfs(board, x, y);   // 启动扩散
    return board;
}

• 核心逻辑：
  • 优先处理特殊情况（点击地雷），直接标记为'X'并终止；
  • 对空方块，提前标记为'B'（避免重复访问），再调用DFS扩散。

3. DFS函数dfs解析

void dfs(vector<vector<char>>& board, int x, int y) {
    // 步骤1：计算周围地雷数
    int mineCount = 0;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'M') {
            mineCount++;
        }
    }

    // 步骤2：决定是否扩散
    if (mineCount > 0) {
        board[x][y] = mineCount + '0';  // 显示数字，终止递归
        return;
    } else {
        // 向8方向的'E'扩散
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'E') {
                board[nx][ny] = 'B';  // 提前标记
                dfs(board, nx, ny);
            }
        }
    }
}

• 步骤1（计算地雷数）：遍历8方向，统计合法范围内的'M'数量；
• 步骤2（扩散逻辑）：
  • 若有地雷（mineCount>0）：更新为数字字符（如'1'），终止递归；
  • 若无地雷（mineCount=0）：向8方向的'E'扩散，提前标记为'B'避免重复递归。

4. 关键技巧：避免重复访问
以(3,0)和(2,0)为例：

• (3,0)扩散时，将(2,0)标记为'B'并递归；
• (2,0)递归时，检测到(3,0)已为'B'（非'E'），不再重复处理。
• 若不提前标记，会导致无限递归（栈溢出）。

时间与空间复杂度分析

• 时间复杂度：O(m*n)
  每个格子最多被访问1次（标记后不再处理），每次处理含8方向遍历（常数时间）。

• 空间复杂度：O(m*n)
  递归栈深度最坏为m*n（全为'E'时遍历所有格子），标记操作无需额外空间。

四、坑点总结 & 拓展思考

坑点总结

1. 8方向边界检查：nx和ny必须在[0, m)和[0, n)范围内，否则越界；
2. 数字字符转换：mineCount + '0'依赖ASCII码（如2 + '0' = '2'），仅适用于1-8；
3. 递归终止条件：mineCount>0时必须return，否则会覆盖数字；
4. 提前标记：'E'→'B'是避免重复递归的核心，不可遗漏。

拓展思考

• 若用BFS实现，队列需存储待扩散的坐标，如何修改代码？
• 若网格中存在已标记的地雷（如'X'），代码需要如何调整？

下次我们要攻克的题目是力扣 LCR 130. 衣橱整理 👇

题目链接：LCR 130. 衣橱整理

感兴趣的小伙伴可以提前思考：

• 如何高效计算坐标的数位和？
• 如何避免重复访问同一格子？
• DFS 和 BFS 哪种实现更简洁？

蹲一波更新，带你从思路拆解到代码实现，手把手搞定这道经典网格问题～ 😊

通过这道题，能掌握8方向遍历、递归扩散、状态标记等核心技巧，为解决复杂网格问题打下基础。欢迎在评论区分享你的思路，一起交流进步~ 🌟

喜欢的话点个赞吧~ 关注一波，后续更新不迷路！😉