英文原文
Let's play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
'M'represents an unrevealed mine,'E'represents an unrevealed empty square,'B'represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),- digit (
'1'to'8') represents how many mines are adjacent to this revealed square, and 'X'represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares ('M' or 'E').
Return the board after revealing this position according to the following rules:
- If a mine
'M'is revealed, then the game is over. You should change it to'X'. - If an empty square
'E'with no adjacent mines is revealed, then change it to a revealed blank'B'and all of its adjacent unrevealed squares should be revealed recursively. - If an empty square
'E'with at least one adjacent mine is revealed, then change it to a digit ('1'to'8') representing the number of adjacent mines. - Return the board when no more squares will be revealed.
Example 1:
Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0] Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
Example 2:
Input: board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2] Output: [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 50board[i][j]is either'M','E','B', or a digit from'1'to'8'.click.length == 20 <= clickr < m0 <= clickc < nboard[clickr][clickc]is either'M'or'E'.
中文题目
让我们一起来玩扫雷游戏！
给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：
'M'代表一个 未挖出的 地雷，'E'代表一个 未挖出的 空方块，'B'代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，- 数字（
'1'到'8'）表示有多少地雷与这块 已挖出的 方块相邻， 'X'则表示一个 已挖出的 地雷。
给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（'M' 或者 'E'）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。
根据以下规则，返回相应位置被点击后对应的盘面：
- 如果一个地雷（
'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.lengthn == board[i].length1 <= m, n <= 50board[i][j]为'M'、'E'、'B'或数字'1'到'8'中的一个click.length == 20 <= clickr < m0 <= clickc < nboard[clickr][clickc]为'M'或'E'
通过代码
高赞题解
🙋 今日打卡！
一、题目分析
给定初始二维数组和起点，返回修改后的二维数组。
- 若起点处是雷，即 ‘M’，直接将其修改为 ‘X’，游戏结束；
- 若起点处是空，即 ‘E’，则从起点开始向 8 邻域中的空地搜索，直到到达邻接💥的空地停止。
- 和二叉树从根结点开始搜索，直到达到叶子节点停止，是几乎一样的，所以会写二叉树的 BFS/DFS，那么这题也就写出来了。
二、代码实现
DFS 代码
class Solution {
// 定义 8 个方向
int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
int[] dy = {0, 0, -1, 1, -1, 1, 1, -1};
public char[][] updateBoard(char[][] board, int[] click) {
int x = click[0], y = click[1];
// 1. 若起点是雷，游戏结束，直接修改 board 并返回。
if (board[x][y] == 'M') {
board[x][y] = 'X';
} else { // 2. 若起点是空地，则从起点开始向 8 邻域的空地进行深度优先搜索。
dfs(board, x, y);
}
return board;
}
private void dfs(char[][] board, int i, int j) {
// 递归终止条件：判断空地 (i, j) 周围是否有雷，若有，则将该位置修改为雷数，终止该路径的搜索。
int cnt = 0;
for (int k = 0; k < 8; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
continue;
}
if (board[x][y] == 'M') {
cnt++;
}
}
if (cnt > 0) {
board[i][j] = (char)(cnt + '0');
return;
}
// 若空地 (i, j) 周围没有雷，则将该位置修改为 ‘B’，向 8 邻域的空地继续搜索。
board[i][j] = 'B';
for (int k = 0; k < 8; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'E') {
continue;
}
dfs(board, x, y);
}
}
}BFS 代码
这里要注意的是，与树的 BFS 不一样（每个节点只有一个父亲节点），本题图中的点会由多个点达到，因此需要加上 boolean[][] visited 数组记录访问标志，防止每个点重复入队而超时。
class Solution {
// 定义 8 个方向
int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
int[] dy = {0, 0, -1, 1, -1, 1, 1, -1};
public char[][] updateBoard(char[][] board, int[] click) {
// 1. 若起点是雷，游戏结束，直接修改 board 并返回。
int x = click[0], y = click[1];
if (board[x][y] == 'M') {
board[x][y] = 'X';
return board;
}
// 2. 若起点是空地，则将起点入队，从起点开始向 8 邻域的空地进行宽度优先搜索。
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
visited[x][y] = true;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {x, y});
while (!queue.isEmpty()) {
int[] point = queue.poll();
int i = point[0], j = point[1];
// 判断空地 (i, j) 周围是否有雷
int cnt = 0;
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length) {
continue;
}
if (board[newX][newY] == 'M') {
cnt++;
}
}
// 若空地 (i, j) 周围有雷，则将该位置修改为雷数；否则将该位置更新为 ‘B’，并将其 8 邻域中的空地入队，继续进行 bfs 搜索。
if (cnt > 0) {
board[i][j] = (char)(cnt + '0');
} else {
board[i][j] = 'B';
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length
|| board[newX][newY] != 'E' || visited[newX][newY]) {
continue;
}
visited[newX][newY] = true;
queue.offer(new int[] {newX, newY});
}
}
}
return board;
}
}统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 40793 | 63409 | 64.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
