05 August 2008
这里要注意的是，与树的 BFS 不一样（每个节点只有一个父亲节点），本题图中的点会由多个点达到，因此需要加上 boolean[][] visited 数组记录访问标志，防止每个点重复入队而超时。
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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 count = 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') {
count++;
}
}
// 若空地 (i, j) 周围有雷，则将该位置修改为雷数；否则将该位置更新为 ‘B’，并将其 8 邻域中的空地入队，继续进行 bfs 搜索。
if (count > 0) {
board[i][j] = (char) (count + '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;
}
}
给定初始二维数组和起点，返回修改后的二维数组。
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 count = 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’) { count++; } } if (count > 0) { board[i][j] = (char) (count + ‘0’); return; }
1
2
3
4
5
6
7
8
9
10
// 若空地 (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);
} } } ```