LeetCode 529. 扫雷游戏

约 7 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为
标签
数组 深度优先搜索 广度优先搜索 矩阵

题目描述

✅ 529. 扫雷游戏

image-20260928224310700

image-20260928224310702

image-20260928224310704

image-20260928224310706

题意分析

点击未揭露的地雷 M 时，只把它改成 X，游戏结束。点击未揭露的空格 E 时，若周围八个方向有雷，就显示雷数；若没有雷，就显示空白 B，并继续揭露它周围的未揭露格子。

自动扩展只会穿过周围无雷的空格，数字格是扩展的边界。目标是按这一规则更新本次点击能揭露的区域，其余格子保持原状。

解法：DFS 模拟展开

核心思路

[!blue]

入口先单独处理直接点中 M 的情况，其余情况从点击位置做 DFS。递归只处理仍为 E 的格子：先检查八邻域，统计其中 M 的数量，边界外的位置不参与统计。

雷数大于零时，把当前格子改为相应数字并立即返回，因为规则只要求揭露这个数字格。雷数为零时，先改为 B，再递归处理界内八邻居。此时邻居中没有地雷，所以自动展开不会引爆地雷。

棋盘字符同时充当访问标记。格子从 E 变成数字或 B 后，再次到达会直接返回，因此相邻空白格不会无限互相递归；标记必须在继续扩展之前写入。

所有能通过无雷邻域空格到达的位置，都会沿着相邻关系被 DFS 访问；每个数字边界会被揭露，但不会再向外传播。这样既不会漏掉应该展开的格子，也不会越过数字边界，多揭露无关区域。

解题步骤

  • 入口处理直接点击地雷。
  • 已揭露格子直接返回。
  • 统计八邻域地雷，非零则写数字并返回。
  • 否则标记 B，再扩展界内邻居。

题目保证点击位置有效且尚未揭露。角落和边缘只统计界内邻居；单个空格会变成 B；点击周围有雷的空格时，只更新当前数字，不继续扩展。

代码实现

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)$。每个空格最多执行一次实质处理，每次统计和扩展都只检查八邻域；对已揭露格子的重复调用也只有常数数量。
  • 空间复杂度：$O(mn)$，最坏递归栈深度线性，棋盘原地修改。

关键点总结

[!green]

  • 数字格只揭露，B 格才继续扩展，这个区别决定了区域边界。
  • 统计与扩展均包含八个方向，并排除当前位置与越界位置。
  • 先写入揭露状态再递归，让棋盘本身承担访问标记。

易错点总结

[!yellow]

  • 只统计上下左右，会漏掉对角地雷。
  • 数字分支不返回，会继续将数字覆盖为空白并越过边界扩展。
  • 标记放在递归之后，会让相邻空白格反复互相调用。

相似题目

题目 难度 关联与区别
733. 图像渲染 简单 同样从点击点扩散连通区域，本题只有周围雷数为0的格子才继续扩展，数字格只揭开不递归。
200. 岛屿数量 中等 同样通过访问标记避免重复探索，本题更新内容还取决于周围八邻域雷数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/39327240
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！