529. 扫雷游戏
题目描述
输入 m x n 的字符矩阵 board 表示扫雷盘面。'M' 是还没挖开的雷，'E' 是还没挖开的空格，'B' 是已挖开且周围 8 格都没有雷的空格，'1' 到 '8' 是已挖开的格子并表示周围 8 格中雷的个数，'X' 是已挖开的雷。
输入 click = [r, c]，表示要挖开第 r 行第 c 列（下标从 0 开始）的格子，该格一定是 'M' 或 'E'。
挖到 'M' 时，把它改成 'X'，游戏结束。挖到 'E' 时，先数它周围 8 格里的雷：若有雷，就把它改成对应的数字字符；若一个都没有，就改成 'B'，并继续对周围 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"]]
解释：点到左下角空白处，连片展开空白区域，雷周围的格子显示数字 1，雷本身和被数字隔开的 (0,2) 保持未挖开。
示例 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,2)，把它改成 'X'，其余格子不变。
数据范围
m == board.lengthn == board[i].length1 <= m, n <= 50board[i][j]是'M'、'E'、'B'或'1'到'8'中的一个。click.length == 20 <= click[0] < m0 <= click[1] < nboard[click[0]][click[1]]是'M'或'E'。
解题思路：广度优先搜索
这是从点击格出发的 BFS。每出队一个格子，先数它周围 8 格的雷：有雷就写数字并停下（数字格是揭开区域的边界）；没有雷就写 B，再把周围仍是 E 且没入过队的格子入队。只有 B 格才会继续扩散，所以揭开的区域被一圈数字包住。
为什么正确
队列里的格子都是待揭开的 E 格；seen 保证每个格子最多入队一次，因此每格只被处理一次。
复杂度分析
时间 O(mn)，每格最多处理一次、每次查看 8 个邻居；空间 O(mn)。
易错点
只有周围没有雷的格子才能扩展。如果数字格也把邻居入队，就会把不该揭开的格子揭开；另外要在入队时标记，避免同一格重复入队。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
r, c = click
if board[r][c] == 'M':
board[r][c] = 'X'
return board
m, n = len(board), len(board[0])
dirs = [(dx, dy) for dx in (-1, 0, 1) for dy in (-1, 0, 1) if dx or dy]
queue = collections.deque([(r, c)])
seen = {(r, c)}
while queue:
x, y = queue.popleft()
mines = 0
for dx, dy in dirs:
i, j = x + dx, y + dy
if 0 <= i < m and 0 <= j < n and board[i][j] == 'M':
mines += 1
if mines > 0:
board[x][y] = str(mines)
continue
board[x][y] = 'B'
for dx, dy in dirs:
i, j = x + dx, y + dy
if 0 <= i < m and 0 <= j < n and board[i][j] == 'E' and (i, j) not in seen:
seen.add((i, j))
queue.append((i, j))
return boardclass Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
return board;
}
int m = board.length, n = board[0].length;
int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{r, c});
boolean[][] seen = new boolean[m][n];
seen[r][c] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
int mines = 0;
for (int[] d : dirs) {
int i = x + d[0], j = y + d[1];
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'M') {
mines++;
}
}
if (mines > 0) {
board[x][y] = (char) ('0' + mines);
continue;
}
board[x][y] = 'B';
for (int[] d : dirs) {
int i = x + d[0], j = y + d[1];
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'E' && !seen[i][j]) {
seen[i][j] = true;
queue.offer(new int[]{i, j});
}
}
}
return board;
}
}class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
return board;
}
int m = board.size(), n = board[0].size();
vector<pair<int, int>> dirs;
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
if (dx || dy) dirs.push_back({dx, dy});
deque<pair<int, int>> q;
q.push_back({r, c});
set<pair<int, int>> seen;
seen.insert({r, c});
while (!q.empty()) {
auto [x, y] = q.front();
q.pop_front();
int mines = 0;
for (auto [dx, dy] : dirs) {
int i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'M') {
mines++;
}
}
if (mines > 0) {
board[x][y] = '0' + mines;
continue;
}
board[x][y] = 'B';
for (auto [dx, dy] : dirs) {
int i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'E' && !seen.count({i, j})) {
seen.insert({i, j});
q.push_back({i, j});
}
}
}
return board;
}
};func updateBoard(board [][]byte, click []int) [][]byte {
r, c := click[0], click[1]
if board[r][c] == 'M' {
board[r][c] = 'X'
return board
}
m, n := len(board), len(board[0])
dirs := [][2]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}
queue := [][2]int{{r, c}}
seen := map[[2]int]bool{{r, c}: true}
for len(queue) > 0 {
x, y := queue[0][0], queue[0][1]
queue = queue[1:]
mines := 0
for _, d := range dirs {
i, j := x+d[0], y+d[1]
if 0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'M' {
mines++
}
}
if mines > 0 {
board[x][y] = byte('0' + mines)
continue
}
board[x][y] = 'B'
for _, d := range dirs {
i, j := x+d[0], y+d[1]
if 0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'E' && !seen[[2]int{i, j}] {
seen[[2]int{i, j}] = true
queue = append(queue, [2]int{i, j})
}
}
}
return board
}var updateBoard = function(board, click) {
const [r, c] = click;
if (board[r][c] === 'M') {
board[r][c] = 'X';
return board;
}
const m = board.length, n = board[0].length;
const dirs = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
const queue = [[r, c]];
const seen = new Set([r * n + c]);
while (queue.length > 0) {
const [x, y] = queue.shift();
let mines = 0;
for (const [dx, dy] of dirs) {
const i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] === 'M') {
mines++;
}
}
if (mines > 0) {
board[x][y] = String(mines);
continue;
}
board[x][y] = 'B';
for (const [dx, dy] of dirs) {
const i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] === 'E' && !seen.has(i * n + j)) {
seen.add(i * n + j);
queue.push([i, j]);
}
}
}
return board;
};function updateBoard(board: string[][], click: number[]): string[][] {
const [r, c] = click;
if (board[r][c] === 'M') {
board[r][c] = 'X';
return board;
}
const m = board.length, n = board[0].length;
const dirs = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
const queue = [[r, c]];
const seen = new Set([r * n + c]);
while (queue.length > 0) {
const [x, y] = queue.shift();
let mines = 0;
for (const [dx, dy] of dirs) {
const i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] === 'M') {
mines++;
}
}
if (mines > 0) {
board[x][y] = String(mines);
continue;
}
board[x][y] = 'B';
for (const [dx, dy] of dirs) {
const i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] === 'E' && !seen.has(i * n + j)) {
seen.add(i * n + j);
queue.push([i, j]);
}
}
}
return board;
}其他解法
BFS 用队列逐圈展开，需要单独的访问标记防止重复入队；DFS 递归展开，直接用格子状态判重，两者复杂度相同。
解法 2：深度优先搜索 时间 O(mn)，空间 O(mn)
从点击位置递归。先统计周围 8 格的地雷数，若不为 0，就写上数字并停止。否则标记为 B，再对周围仍为 E 的格子递归展开。修改后的格子不再是 E，所以不会被重复访问，也不需要额外的访问集合。
代码更短，利用棋盘本身的状态判重。递归深度最坏可达 m·n，棋盘很大时有栈溢出风险。
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
r, c = click
if board[r][c] == 'M':
board[r][c] = 'X'
return board
m, n = len(board), len(board[0])
def dfs(x, y):
# 统计周围 8 格的地雷数
mines = 0
for i in range(x - 1, x + 2):
for j in range(y - 1, y + 2):
if 0 <= i < m and 0 <= j < n and board[i][j] == 'M':
mines += 1
if mines:
board[x][y] = str(mines)
return
# 先标记为 B 再递归，避免重复访问
board[x][y] = 'B'
for i in range(x - 1, x + 2):
for j in range(y - 1, y + 2):
if 0 <= i < m and 0 <= j < n and board[i][j] == 'E':
dfs(i, j)
dfs(r, c)
return boardclass Solution {
private int m, n;
private void dfs(char[][] board, int x, int y) {
int mines = 0;
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'M') mines++;
if (mines > 0) {
board[x][y] = (char) ('0' + mines);
return;
}
board[x][y] = 'B';
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'E') dfs(board, i, j);
}
public char[][] updateBoard(char[][] board, int[] click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
return board;
}
m = board.length;
n = board[0].length;
dfs(board, r, c);
return board;
}
}class Solution {
public:
int m, n;
void dfs(vector<vector<char>>& board, int x, int y) {
int mines = 0;
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'M') mines++;
if (mines) {
board[x][y] = '0' + mines;
return;
}
board[x][y] = 'B';
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'E') dfs(board, i, j);
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
return board;
}
m = board.size();
n = board[0].size();
dfs(board, r, c);
return board;
}
};func updateBoard(board [][]byte, click []int) [][]byte {
r, c := click[0], click[1]
if board[r][c] == 'M' {
board[r][c] = 'X'
return board
}
m, n := len(board), len(board[0])
var dfs func(x, y int)
dfs = func(x, y int) {
mines := 0
for i := x - 1; i <= x+1; i++ {
for j := y - 1; j <= y+1; j++ {
if i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'M' {
mines++
}
}
}
if mines > 0 {
board[x][y] = byte('0' + mines)
return
}
board[x][y] = 'B'
for i := x - 1; i <= x+1; i++ {
for j := y - 1; j <= y+1; j++ {
if i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'E' {
dfs(i, j)
}
}
}
}
dfs(r, c)
return board
}var updateBoard = function(board, click) {
const [r, c] = click;
if (board[r][c] === 'M') {
board[r][c] = 'X';
return board;
}
const m = board.length, n = board[0].length;
const dfs = (x, y) => {
let mines = 0;
for (let i = x - 1; i <= x + 1; i++)
for (let j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] === 'M') mines++;
if (mines > 0) {
board[x][y] = String(mines);
return;
}
board[x][y] = 'B';
for (let i = x - 1; i <= x + 1; i++)
for (let j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] === 'E') dfs(i, j);
};
dfs(r, c);
return board;
};function updateBoard(board: string[][], click: number[]): string[][] {
const [r, c] = click;
if (board[r][c] === 'M') {
board[r][c] = 'X';
return board;
}
const m = board.length, n = board[0].length;
const dfs = (x: number, y: number): void => {
let mines = 0;
for (let i = x - 1; i <= x + 1; i++)
for (let j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] === 'M') mines++;
if (mines > 0) {
board[x][y] = String(mines);
return;
}
board[x][y] = 'B';
for (let i = x - 1; i <= x + 1; i++)
for (let j = y - 1; j <= y + 1; j++)
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] === 'E') dfs(i, j);
};
dfs(r, c);
return board;
}