侧边栏壁纸
博主头像
Hope博主等级

努力赚钱的工科研究生

  • 累计撰写 362 篇文章
  • 累计创建 129 个标签
  • 累计收到 5 条评论
标签搜索

LeetCode 529. 扫雷游戏

Hope
2022-03-06 / 2 评论 / 0 点赞 / 1,929 阅读 / 1,021 字
温馨提示:
本文最后更新于 2022-03-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

LeetCode 529. 扫雷游戏

思路:
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);
            }
        }
    }
};
0

评论区