思路:
dfs
代码:
class Solution {
public:
int n , m;
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
n = board.size(),m = board[0].size();
int x = click[0],y = click[1];
//如果入口就是一个地雷 可以直接退出
if(board[x][y] == 'M'){
board[x][y] = 'X';
return board;
}
dfs(board,x,y);
return board;
}
void dfs(vector<vector<char>> &board,int x,int y){
//如果是一个被打开的 或者是一个地雷 就没必要去搜索了
if(board[x][y] != 'E' || board[x][y] == 'M' || board[x][y] == 'X') return;
//s 表示统计一个格子附近地雷的个数
int s = 0;
//我们统计的是(x,y)的周围几个格子 但是需要注意的一点是 可能会越界 所以有个max和min的操作
for(int i = max(0 , x - 1);i <= min(n - 1, x + 1);i++){
for(int j = max(0 , y - 1); j <= min(m - 1, y + 1);j++){
//如果枚举到(x,y)我们不需要去统计
if(i == x && j == y) continue;
//如果是M 表示一个未挖出的地雷 X 表示已经挖出的地雷 我们都要算在内
if(board[i][j] == 'M' || board[x][y] == 'X') s++;
}
}
//如果(x,y)附近有地雷
if(s){
board[x][y] = '0' + s;
return;
}
//如果没有地雷 注意上面如果有地雷直接return了
//如果没有地雷 我们再去搜附近的点 同时标记这个点附近没有地雷
board[x][y] = 'B';
for(int i = max(0 , x - 1);i <= min(n - 1, x + 1);i++){
for(int j = max(0 , y - 1); j <= min(m - 1, y + 1);j++){
if(i == x && j == y) continue;
dfs(board,i,j);
}
}
}
};
评论区