(dfs) leetcode 528. Minesweeper

今天药忘吃喽~ 2021-12-09 15:57 182阅读 0赞

![1266918-20190710184104008-1251752531.png][]

![1266918-20190710184217197-394228754.png][]

![1266918-20190710184233283-1283138277.png][]

思路：这道题和小岛那道有些类似，主要是实现以下这四个操作：

1.  If a mine ('M') is revealed, then the game is over - change it to **'X'**.   若点到M，它是代表还未发现的炸弹，则该位置变为X，游戏结束。
2.  If an empty square ('E') with **no adjacent mines** is revealed, then change it to revealed blank ('B') and all of its adjacent **unrevealed** squares should be revealed recursively.    如果点到E，它的四周没有炸弹，则该位置变为B，然后递归遍历它附近的8个格子（用dfs）。
3.  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.   如果点到E，它的四周至少有一个炸弹，则把该位置变为1-8（为炸弹的个数）。
4.  Return the board when no more squares will be revealed.   返回board。

class Solution {
    public:
        int dx[8] = {-1,-1,-1, 1, 1, 1,0,0};
        int dy[8] = {-1, 0, 1,-1, 0, 1,-1,1};
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
            //If a mine ('M') is revealed, then the game is over - change it to 'X'.
            int x = click[0], y = click[1];
            if(board[x][y]=='M'){
                board[x][y] = 'X';
                return board;
            }
            //If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
            dfs(board, x, y);
            return board;
            
        }
        
        void dfs(vector<vector<char>>& board, int x, int y){
            int m = board.size(), n = board[0].size();
            if(x<0 || x>=m || y<0 || y>=n || board[x][y] !='E')
                //出口
                return;
            int num = numOfBombs(board, x, y);
            //1. no adjacenet mine
            if(num==0){
                board[x][y] = 'B';
                for(int i=0; i<8; i++){
                    int newX = x + dx[i], newY = y + dy[i];
                    dfs(board, newX, newY);
                }
            }
            else{
                //2. at least one mine
                board[x][y] = num +'0';
            }
        }
        
        int numOfBombs(vector<vector<char>>& board, int x, int y){
            int num = 0;  //记录附近8个格子中炸弹的个数
            int m = board.size(), n = board[0].size();
            for(int i=0; i<8; ++i){
                //遍历附近的8格
                int newX = x +dx[i], newY = y +dy[i];
                if(newX<0 || newX>=m || newY<0 || newY>=n)
                    continue;
                if(board[newX][newY]=='M' || board[newX][newY]=='X')
                    ++num;
            }
            return num;
        }
    };

转载于:https://www.cnblogs.com/Bella2017/p/11165914.html

[1266918-20190710184104008-1251752531.png]: /images/20211209/e25d7eb7e136415483975b290ef924cd.png
[1266918-20190710184217197-394228754.png]: /images/20211209/57de9806628d426cb5d2fe8a02b9a568.png
[1266918-20190710184233283-1283138277.png]: /images/20211209/72a0188732294f4fabc07cb1c6092174.png