题目链接
529. 扫雷游戏
题目描述
让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
- 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
- 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。
- 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
- 如果在此次点击中，若无更多方块可被揭露，则返回面板。
解题思路
典型的BFS或者DFS。
1.DFS
给定初始二维数组和起点，返回修改后的二维数组。
- 若起点处是雷，即 ‘M’，直接将其修改为 'X'，游戏结束；
- 若起点处是空，即 ‘E’，则从起点开始向 8 邻域中的空地搜索，判断8邻域是否有炸弹，如果有就把该坐标的值修改为炸弹的个数并退出，如果没有则把该坐标的值按照题目的要求修改为“B”。继续对其8邻域搜索即可
写DFS相关题目的时候，只要把边界条件，递归条件判断好就行了，这也是比较难的地方。
2.BFS
BFS就是利用队列来实现，依葫芦画瓢就OK了
AC代码
1.DFS
class Solution {
int dir[][] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
public char[][] updateBoard(char[][] board, int[] click) {
int x = click[0];
int y = click[1];
if(board[x][y] == 'M'){
board[x][y] = 'X';
return board;
}
else dfs(board,x,y);
return board;
}
void dfs(char[][] board,int x,int y){
if(x<0||x>=board.length||y<0||y>=board[0].length) return;
if(board[x][y] != 'E') return;
int cnt = 0;
for(int i = 0; i < 8; i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx<0||xx>=board.length||yy<0||yy>=board[0].length) continue;
if(board[xx][yy] == 'M') cnt++;
}
if(cnt>0){
board[x][y] = (char)(cnt+'0');
return;
}else
{
board[x][y] = 'B';
}
for(int i = 0; i < 8; i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
dfs(board,xx,yy);
}
}
}
2.BFS
代码中viewer数组是关键，一开始超时了就是因为把很多重复判断过的点又加入队列中，
DFS可能不需要viewer数组用于记录某点是否遍历过
但是BFS是一定需要的！！！！！
class Solution {
int dir[][] = {{0,1},{0,-1},{-1,0},{1,0},{-1,-1},{1,1},{1,-1},{-1,1}};
Queue<int []> queue = new LinkedList<>();
public char[][] updateBoard(char[][] board, int[] click) {
int x = click[0];
int y = click[1];
// 1. 若起点是雷，游戏结束，直接修改 board 并返回。
if(board[x][y] == 'M'){
board[x][y] = 'X';
return board;
}else{
// 2. 若起点是空地，则将起点入队，从起点开始向 8 邻域的空地进行宽度优先搜索。
int buf[] = {x,y};
queue.offer(buf);
//viewe数组用于记录该坐标点是否以及遍历过！
int viewer[][] = new int[board.length][board[0].length];
while(!queue.isEmpty()){
// 判断空地 (temp[0], temp[1]) 周围是否有雷
int temp[] = queue.poll();
int cnt = 0;
for(int i = 0; i < 8; i++){
int x1 = temp[0] + dir[i][0];
int y1 = temp[1] + dir[i][1];
if(x1<0||x1>=board.length||y1<0||y1>=board[0].length) continue;
if(board[x1][y1] == 'M') cnt++;
}
//若空地(temp[0],temp[1])周围有雷，则将该位置修改为雷数；否则将该位置更新为‘B’,并将其8邻域中的空地入队，继续进行bfs搜索。
if(cnt>0){
board[temp[0]][temp[1]] = (char)('0' + cnt);
}else{
board[temp[0]][temp[1]] = 'B';
for(int i = 0; i < 8; i++){
int x1 = temp[0] + dir[i][0];
int y1 = temp[1] + dir[i][1];
if(x1<0||x1>=board.length||y1<0||y1>=board[0].length||board[x1][y1] != 'E' || viewer[x1][y1] == 1) continue;
viewer[x1][y1] = 1;
queue.offer(new int[]{x1,y1});
}
}
}
return board;
}
}
}