What is the best approach to solve the Minesweeper problem?

The best approach is using Depth-First Search (DFS) combined with array manipulation to reveal cells and calculate adjacent mine counts.

How do you handle edge cases in the Minesweeper problem?

You handle edge cases by carefully checking the boundaries of the grid during DFS traversal and ensuring that all neighboring cells are correctly processed.

Can the Minesweeper problem be solved using Breadth-First Search (BFS)?

Yes, BFS can be used as an alternative to DFS. BFS is especially useful when you want to process all adjacent cells level by level.

What is the time complexity of solving the Minesweeper problem?

The time complexity is O(m * n), where m and n are the dimensions of the board, because in the worst case, all cells must be visited.

How does GhostInterview assist in solving the Minesweeper problem?

GhostInterview provides detailed steps for implementing DFS, guides you through efficient grid traversal, and helps you handle edge cases in Minesweeper.

#529

Medium

auto_awesome图·搜索

LeetCode 题解工作台

扫雷游戏

让我们一起来玩扫雷游戏！给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中： 'M' 代表一个未挖出的地雷， 'E' 代表一个未挖出的空方块， 'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（ '1' 到 '8' …

数组深度优先搜索广度优先搜索矩阵

题目描述

让我们一起来玩扫雷游戏！

给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：

'M' 代表一个 未挖出的 地雷，
'E' 代表一个 未挖出的 空方块，
'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（'1' 到 '8'）表示有多少地雷与这块 已挖出的 方块相邻，
'X' 则表示一个 已挖出的 地雷。

给你一个整数数组 click ，其中 click = [click_r, click_c] 表示在所有 未挖出的 方块（'M' 或者 'E'）中的下一个点击位置（click_r 是行下标，click_c 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X' 。
如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1' 到 '8' ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面。

示例 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"]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 50
board[i][j] 为 'M'、'E'、'B' 或数字 '1' 到 '8' 中的一个
click.length == 2
0 <= click_r < m
0 <= click_c < n
board[click_r][click_c] 为 'M' 或 'E'

lightbulb

解题思路

方法一：DFS

我们记 $click = (i, j)$ ，如果 $board[i][j]$ 等于 'M'，那么直接将 $board[i][j]$ 的值改为 'X' 即可。否则，我们需要统计 $board[i][j]$ 周围的地雷数量 $cnt$ ，如果 $cnt$ 不为 $0$ ，那么将 $board[i][j]$ 的值改为 $cnt$ 的字符串形式。否则，将 $board[i][j]$ 的值改为 'B'，并且递归地搜索处理 $board[i][j]$ 周围的未挖出的方块。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组 $board$ 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        def dfs(i: int, j: int):
            cnt = 0
            for x in range(i - 1, i + 2):
                for y in range(j - 1, j + 2):
                    if 0 <= x < m and 0 <= y < n and board[x][y] == "M":
                        cnt += 1
            if cnt:
                board[i][j] = str(cnt)
            else:
                board[i][j] = "B"
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < m and 0 <= y < n and board[x][y] == "E":
                            dfs(x, y)

        m, n = len(board), len(board[0])
        i, j = click
        if board[i][j] == "M":
            board[i][j] = "X"
        else:
            dfs(i, j)
        return board

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient DFS implementation that minimizes unnecessary checks.
question_mark
Ensure the candidate handles edge cases like clicks on borders and corners.
question_mark
Check if they can correctly update adjacent cells while respecting the grid's boundaries.

warning

常见陷阱

外企场景

error
Not handling recursion depth properly, leading to stack overflow or missing updates.
error
Incorrect boundary checks when accessing neighboring cells, leading to out-of-bounds errors.
error
Failing to efficiently calculate adjacent mines, resulting in incorrect board updates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the board size to handle larger or smaller grids efficiently.
arrow_right_alt
Introduce additional game features like flags or different mine types.
arrow_right_alt
Optimize the algorithm to use Breadth-First Search (BFS) instead of DFS.

help

常见问题

外企场景

继续练习

#463 岛屿的周长 #417 太平洋大西洋水流问题 #695 岛屿的最大面积