LeetCode 529. 扫雷游戏

2021-09-10 HGNULB 约 13 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 529. 扫雷游戏

题意分析

给一个字符矩阵表示的扫雷棋盘和一次点击坐标，要求返回点击之后的棋盘状态。棋盘上 M 是未挖出的地雷，E 是未挖出的空方块，B 是已挖出且周围没有雷的空白块，1 到 8 表示该格周围八个方向上的雷数，X 是被引爆的雷。点击的落点保证是 M 或 E。

规则本身给出了三条互斥的分支，而其中第三条藏着算法信号：「挖出一个周围没有雷的空方块时，与之相邻的所有未挖出方块都应该被递归地揭露」。「递归地揭露」四个字直接点明了这是一次从点击点出发的连通块扩散，扩散的邻接关系是八连通（因为雷数统计用的是八个方向），扩散的终止条件是「当前格周围有雷」——这类格子要写上数字但不再向外扩，它构成了空白区域的边界。

还有一条隐含约束值得注意：扩散过程中不会踩到雷。因为只有「周围雷数为 $0$」的格子才继续扩散，而它周围既然没有雷，那么它的八个邻居里也就不可能有 M。这意味着代码里不需要为「扩散撞到 M」写特判，M 会被 board[r][c] != 'E' 这个条件自然挡住。

边界上要覆盖：点击直接命中 M（只改这一格为 X 就返回，不做任何扩散）；点击的格子周围有雷（只写一个数字就停，不扩散）；整块棋盘全是 E（一次点击把整张图刷成 B）；棋盘只有一行或一列（越界判断必须逐维独立检查）。棋盘规模是 $50 \times 50$ 以内，所以怎么写都不会超时，考点完全落在规则的正确翻译和递归边界的干净程度上。

解法：DFS 模拟展开

核心思路

先看能不能一趟遍历解决。不行——因为一个格子要不要被揭露，取决于它是否与点击点通过「空白区域」相连，这是典型的连通性问题，必须做搜索。所以框架一定是 DFS 或 BFS，从点击点出发做扩散。真正需要想清楚的是扩散的展开条件与终止条件到底挂在哪一步。

一个很自然但会写错的思路是：把「揭露」和「判断能否继续」分成两件事，先把邻居标记好再决定要不要递归。这样写会产生大量重复分支，而且很容易在「邻居是数字格」时既写了数字又继续往外扩。正确的观察是：三条游戏规则其实构成了对单个格子的完整处理函数，而这个函数天然自带递归出口。

于是把 dfs(r, c) 的语义定死为：「把坐标 (r, c) 这一格按规则处理完，并在需要时把处理传播出去」。它维护的不变量是——函数返回时，(r, c) 一定不再是 E；并且如果它变成了 B，那么它的八个邻居也都已经被处理完毕（即整片以它为起点的空白连通块及其数字边界全部处理完）。

有了这条不变量，函数体只需要三步：第一，如果 board[r][c] != 'E' 就直接返回——这一句同时承担了三重职责，既是「已访问」的判重（已经变成 B 或数字的格子不会被二次处理），又是「不碰地雷」的保护（M 不等于 E），还是「不覆盖已有结果」的保证。正因为它把访问标记直接写在了棋盘上，本题不需要额外的 visited 数组，原地修改就是天然的去重。第二，统计周围八格的雷数；大于 $0$ 就把自己改成对应数字字符并立即返回，因为规则明确说数字格不继续扩散。第三，雷数为 $0$ 才把自己改成 B，然后对八个方向递归。

至于点击直接命中 M 的情况，它不属于扩散逻辑的一部分（规则一是独立分支），所以在入口处单独判掉：改成 X 后立刻返回整块棋盘，一步都不搜。

方向枚举用 DIRS = {-1, 0, 1} 的双重循环再跳过 (0, 0)，比手写八元素的 dx[]/dy[] 数组更短也更不容易抄错。countMines 与扩散循环共用同一套越界判断，逻辑对称，白板上写起来很顺。

解题步骤

入口取出 r = click[0]、c = click[1]，先判 board[r][c] == 'M'：成立就置为 'X' 并返回 board。理由：规则一是独立于扩散的终局分支，提前判掉可以让后面的 DFS 只处理「点到空方块」这一种语义，函数职责单一。

否则调用 dfs(board, r, c)，最后返回 board。理由：题目要求原地修改并返回同一块棋盘，不需要拷贝。

dfs 第一行写 if (board[r][c] != 'E') return;。理由：这是整段代码最关键的一行，一句话同时完成判重、避雷、防覆盖三件事；把它放在函数最开头而不是放在递归调用之前，可以省掉八处重复判断，也让越界检查之外不再需要任何前置条件。

调用 countMines 统计八邻域内 M 的个数。理由：必须在修改自身之前统计，因为统计只看邻居不看自己，但如果先把自己改成 B 再统计，代码阅读时容易误以为自身状态参与了计算。

若 mines > 0，令 board[r][c] = (char)('0' + mines) 并 return。理由：mines 取值范围是 $1$ 到 $8$，'0' + mines 正好落在 '1' 到 '8'；这里的 return 是规则三里「周围有雷则不再扩散」的直译，漏掉它会把数字边界当成空白继续往外挖。

否则令 board[r][c] = 'B'，再用 DIRS 双重循环枚举八个方向，跳过 (0, 0)，做越界检查后递归 dfs(board, nr, nc)。理由：先把自己改成 B 再递归，这一步顺序不能反——它相当于「入栈即标记」，否则相邻两个空白格会互相递归，形成无限循环直到栈溢出。

越界检查写成 nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length，四个条件缺一不可。理由：行列必须分别检查上下界，只判一维或只判上界在单行、单列棋盘上会直接数组越界。

以 board = [["E","E","E"],["E","E","M"],["E","E","E"]]、click = [0,0] 走一遍。入口处 board[0][0] = 'E' 不是 M，进入 dfs(0,0)。(0,0) 是 E，统计八邻域（实际只有 (0,1)、(1,0)、(1,1) 在界内）雷数为 $0$，改成 B，向八方向递归。递归到 (0,1)：是 E，它的邻域含 (1,2) = M，雷数为 $1$，写成 '1' 并立即返回，不再往外扩——注意 (0,2) 因此没有被 (0,1) 挖开。递归到 (1,0)：是 E，邻域含 (1,1)、(0,1) 等但没有 M，雷数 $0$，改成 B 并继续扩散；它会递归到 (2,0)（雷数 $0$，变 B）、(2,1)（邻域含 (1,2) = M，雷数 $1$，写 '1' 停）、以及 (1,1)（邻域含 (1,2) = M，雷数 $1$，写 '1' 停）。递归到 (1,1) 时若已被处理则第一行直接返回。最终棋盘为 [["B","1","E"],["B","1","M"],["B","1","E"]]：左侧一列全是 B，中间一列被数字 1 封成边界，右侧的 (0,2) 和 (2,2) 因为被数字边界挡住而保持 E 未挖出，地雷 (1,2) 原样保留——与期望输出完全一致。

代码实现

class Solution {
    private static final int[] DIRS = {-1, 0, 1};

    public char[][] updateBoard(char[][] board, int[] click) {
        int r = click[0];
        int c = click[1];

        if (board[r][c] == 'M') {
            board[r][c] = 'X';
            return board;
        }

        dfs(board, r, c);
        return board;
    }

    private void dfs(char[][] board, int r, int c) {
        if (board[r][c] != 'E') {
            return;
        }

        int mines = countMines(board, r, c);
        if (mines > 0) {
            board[r][c] = (char) ('0' + mines);
            return;
        }

        board[r][c] = 'B';

        for (int dr : DIRS) {
            for (int dc : DIRS) {
                if (dr == 0 && dc == 0) {
                    continue;
                }

                int nr = r + dr;
                int nc = c + dc;
                if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
                    continue;
                }

                dfs(board, nr, nc);
            }
        }
    }

    private int countMines(char[][] board, int r, int c) {
        int count = 0;
        for (int dr : DIRS) {
            for (int dc : DIRS) {
                if (dr == 0 && dc == 0) {
                    continue;
                }

                int nr = r + dr;
                int nc = c + dc;
                if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
                    continue;
                }

                if (board[nr][nc] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }
}

func updateBoard(board [][]byte, click []int) [][]byte {
    r, c := click[0], click[1]
    if board[r][c] == 'M' {
        board[r][c] = 'X'
        return board
    }

    dfsMines(board, r, c)
    return board
}

func dfsMines(board [][]byte, r int, c int) {
    if board[r][c] != 'E' {
        return
    }

    mines := countMines(board, r, c)
    if mines > 0 {
        board[r][c] = byte('0' + mines)
        return
    }

    board[r][c] = 'B'

    for dr := -1; dr <= 1; dr++ {
        for dc := -1; dc <= 1; dc++ {
            if dr == 0 && dc == 0 {
                continue
            }
            nr := r + dr
            nc := c + dc
            if nr < 0 || nr >= len(board) || nc < 0 || nc >= len(board[0]) {
                continue
            }
            dfsMines(board, nr, nc)
        }
    }
}

func countMines(board [][]byte, r int, c int) int {
    count := 0
    for dr := -1; dr <= 1; dr++ {
        for dc := -1; dc <= 1; dc++ {
            if dr == 0 && dc == 0 {
                continue
            }
            nr := r + dr
            nc := c + dc
            if nr < 0 || nr >= len(board) || nc < 0 || nc >= len(board[0]) {
                continue
            }
            if board[nr][nc] == 'M' {
                count++
            }
        }
    }
    return count
}

复杂度分析

时间复杂度：$O(mn)$，其中 $m$、$n$ 是棋盘的行数和列数。每个格子最多进入 dfs 的主体一次（第二次进来会被首行的 != 'E' 挡回），主体内 countMines 与方向循环各做常数次（$8$ 次）操作，因此总量是 $8 \times O(mn) = O(mn)$。

空间复杂度：$O(mn)$，来自递归调用栈。最坏情况是整块棋盘没有一颗雷，一次点击会把所有格子串成一条深度为 $mn$ 的递归链；棋盘本身是原地修改，没有额外的 visited 数组或队列，所以除递归栈外是 $O(1)$。

关键点总结

当矩阵本身可以被就地改写时，用状态字符代替 visited 数组是最省事的判重方式。本题把「已挖出」编码进了 B 和数字字符，于是一句 if (board[r][c] != 'E') return; 就顶替了访问标记、避障和防覆盖三套逻辑，代码量减半。这个套路在岛屿类题目里同样通用（把 '1' 沉成 '0'）。

递归函数的语义要能用一句话说清，并且出口写在函数第一行，而不是散落在每个递归调用点之前。前者只需一处判断，后者要在八个方向上各写一遍，白板上必错其一。

「扩散有边界」的题型要分清参与扩散的格子和只被标记不再扩散的格子。本题数字格属于后者，它写完数字必须 return；忘记这个 return 会把整张图挖穿，是最常见的错误。

标记必须发生在递归之前（相当于 BFS 的「入队即标记」）。先递归后标记会让相邻空白格互相调用，直接栈溢出。

面试视角：华为很爱考这题，因为它形式简单但规则条目多，能考察读题严谨度。答题时最好先把三条规则逐条复述并映射到代码分支，再动手写；写完主动指出「扩散过程中不可能撞到雷，因为只有周围雷数为 0 才继续扩」，这个观察能证明你真的推演过而不是背模板。如果面试官追问「棋盘很大会不会栈溢出」，标准回答是把 DFS 换成显式队列的 BFS，逻辑一字不改，只把递归改成入队。

易错点总结

错误写法：mines > 0 时写完数字却忘了 return，继续向八个方向递归 → 用例 [["E","E","E"],["E","E","M"],["E","E","E"]]，click = [0,0] → 数字格 (0,1) 会继续挖开 (0,2)，输出右上角变成 B 而不是保持 E，与期望不符。

错误写法：把标记 board[r][c] = 'B' 放在八方向递归循环之后 → 用例 [["E","E"],["E","E"]]，click = [0,0] → (0,0) 递归到 (0,1)，(0,1) 又看到 (0,0) 仍是 E 而递归回去，两格无限互相调用，栈溢出。

错误写法：只用四个方向（上下左右）做扩散和雷数统计 → 用例 [["E","E","E"],["E","M","E"],["E","E","E"]]，click = [0,0] → 对角线上的雷数漏统计，(0,0) 被误判为雷数 $0$ 而挖成 B，正确答案应是 '1'。

错误写法：越界检查只判上界写成 if (nr >= board.length || nc >= board[0].length) continue; → 用例任意 click = [0,0] → nr = -1 时下标为负，Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。

错误写法：入口处点到 M 时改成 X 后没有直接返回，仍继续调用 dfs → 用例 [["B","1","E","1","B"],["B","1","M","1","B"]]，click = [1,2] → dfs 首行看到 board[1][2] 已是 X 不等于 E 虽会返回，但如果 dfs 写成先统计再判重，就会把 X 覆盖成数字，结果丢失引爆标记。

错误写法：把递归出口写成 if (board[r][c] == 'B') return; 而不是 != 'E' → 用例 [["E","M"],["E","E"]]，click = [1,0] → M 不等于 B，扩散会走进地雷格并把它改写成数字，地雷凭空消失。

错误写法：数字字符用 board[r][c] = (char) mines 而不是 (char)('0' + mines) → 用例任意周围有 $1$ 颗雷的点击 → 写入 ASCII 码为 $1$ 的控制字符而不是字符 '1'，输出全是不可见字符。

错误写法：额外开一个 visited[][] 并在 countMines 里也检查 visited → 用例 [["E","M","E"]]，click = [0,0] → 统计雷数时把已访问的格子跳过，(0,0) 的雷数少算，被错判成 B 并把 M 挖开。

错误写法：countMines 里统计条件写成 board[nr][nc] == 'M' || board[nr][nc] == 'X' 之外还漏了任何一种雷的表示，或者反过来把已挖出的数字格也算进雷数 → 用例二次点击后的棋盘 → 雷数统计偏大，本该是 B 的格子被写成数字，空白区域无法展开。

错误写法：方向枚举时忘记 if (dr == 0 && dc == 0) continue; → 用例任意 click → dfs 会对自身递归；虽然首行判重能挡住不至于死循环，但 countMines 会把自己也算一遍，若自身是 M 则雷数多 $1$，数字全部偏大。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	同为原地改写代替 `visited`，但要在外层循环里统计连通块个数
733. 图像渲染	简单	最纯粹的四连通洪泛，没有「数字边界」这种不再扩散的中间态
130. 被围绕的区域	中等	需要反向思考，从边界向内染色标记「不该被填充」的区域
1020. 飞地的数量	中等	从边界出发扩散后统计剩余格子数，考察扩散起点的选择
289. 生命游戏	中等	同样统计八邻域，但要求所有格子同时更新，需用编码技巧保存新旧两态