LeetCode 扫雷游戏（深度优先搜索、广度优先搜索）

让我们一起来玩扫雷游戏！

给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，‘E’ 代表一个未挖出的空方块，‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（‘1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，‘X’ 则表示一个已挖出的地雷。

现在给出在所有未挖出的方块中（‘M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。

示例 1：
输入:
[[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘M’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘E’, ‘E’, ‘E’]]
Click : [3,0]
输出:
[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]
解释:

示例 2：
输入:
[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]
Click : [1,2]
输出:
[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘X’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]
解释:

注意：
输入矩阵的宽和高的范围为 [1,50]。
点击的位置只能是未被挖出的方块 (‘M’ 或者 ‘E’)，这也意味着面板至少包含一个可点击的方块。
输入面板不会是游戏结束的状态（即有地雷已被挖出）。
简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。
思路分析： 典型的深度、广度优先搜索题。
方法一：深度优先搜索法。

class Solution {
public:
    int rowSize, colSize;
    int rowMove[8]={1,1,1,0,0,-1,-1,-1};
    int colMove[8]={1,0,-1,1,-1,-1,0,1};  //八个方向
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        rowSize = board.size(), colSize = board[0].size();
        int row = click[0], col = click[1]; //先把坐标取出来
         //如果为 M 结束
        if(board[row][col]=='M'){
            board[row][col]='X';
            return board;
        }
        //否则 不是M dfs遍历
        dfs(board,row, col);
        return board;
    }
        void dfs(vector<vector<char>>& board, int row, int col){
        int mines = 0;  
        //统计周围八个方向雷的总个数
        for(int i = 0; i < 8; ++i){
            int nextRow = row + rowMove[i];
            int nextCol =col + colMove[i];
            if(nextRow >= 0 && nextRow < rowSize && nextCol >= 0 && nextCol < colSize){
                if(board[nextRow][nextCol] == 'M')
                    mines++;
            }
        }
        //如果没有周围没有雷 此位置改为‘B’ 继续遍历dfs  否则此位置改为雷的个数
        if(mines==0){
            board[row][col]='B';
            //对八个方向进行尝试移动
            for(int i = 0; i < 8; ++i){
                int nextRow = row + rowMove[i];
                int nextCol =col + colMove[i];
                if(nextRow >= 0 && nextRow < rowSize && nextCol >= 0 && nextCol < colSize){
                    if(board[nextRow][nextCol] == 'E'){
                        dfs(board, nextRow, nextCol);
                    }
                       
                }
            }    
        }
        else{
            board[row][col] = '0' + mines;
        }
    }
}; 

方法二：广度优先遍历法。

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int rowMove[8]={1,1,1,0,0,-1,-1,-1};
        int colMove[8]={1,0,-1,1,-1,-1,0,1};  //八个方向
        int rowSize = board.size(), colSize = board[0].size();
        vector<vector<bool>> flag(rowSize, vector<bool>(colSize, false));
         //如果为 M 结束
        if(board[click[0]][click[1]]=='M'){
            board[click[0]][click[1]]='X';
            return board;
        }
        queue<int> myQue;//辅助队列
        myQue.push(click[0]);//约定：先放行，再放列
        myQue.push(click[1]);
        flag[click[0]][click[1]] = true;
        while (!myQue.empty()){
        	//约定：先取行，再取列
            int row = myQue.front();
            myQue.pop();
            int col = myQue.front();
            myQue.pop();
            int mines = 0;  
            //统计周围八个方向雷的总个数
            for(int i = 0; i < 8; ++i){
                int nextRow = row + rowMove[i];
                int nextCol =col + colMove[i];
                if(nextRow >= 0 && nextRow < rowSize && nextCol >= 0 && nextCol < colSize){
                    if(board[nextRow][nextCol] == 'M')
                        mines++;
                }
            }
            //如果没有周围没有雷 此位置改为‘B’ 放入队列 否则此位置改为雷的个数
            if(mines==0){
                board[row][col]='B';
                //对八个方向进行尝试移动
                for(int i = 0; i < 8; ++i){
                    int nextRow = row + rowMove[i];
                    int nextCol =col + colMove[i];
                    if(nextRow >= 0 && nextRow < rowSize && nextCol >= 0 && nextCol < colSize && flag[nextRow][nextCol] == false){
                        if(board[nextRow][nextCol] == 'E'){
                            myQue.push(nextRow);//约定：先放行，再放列
                            myQue.push(nextCol);
                            flag[nextRow][nextCol] = true;
                        }

                    }
                }    
            }
            else{
                board[row][col] = '0' + mines;
            }
        }
        return board;
    }
};