扫雷游戏的递归解法
目录
一，题目
二，题目接口
三，解题思路
四，解题代码
一，题目
让我们一起来玩扫雷游戏！
给你一个大小为
m x n二维字符矩阵board，表示扫雷游戏的盘面，其中：
'M'代表一个 未挖出的 地雷，'E'代表一个 未挖出的 空方块，'B'代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，- 数字（
'1'到'8'）表示有多少地雷与这块 已挖出的 方块相邻，'X'则表示一个 已挖出的 地雷。给你一个整数数组
click，其中click = [clickr, clickc]表示在所有 未挖出的 方块（'M'或者'E'）中的下一个点击位置（clickr是行下标，clickc是列下标）。根据以下规则，返回相应位置被点击后对应的盘面：
- 如果一个地雷（
'M'）被挖出，游戏就结束了- 把它改为'X'。- 如果一个 没有相邻地雷 的空方块（
'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。- 如果一个 至少与一个地雷相邻 的空方块（
'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。- 如果在此次点击中，若无更多方块可被揭露，则返回盘面。
二，题目接口
class Solution {
public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {}
};三，解题思路
对于这道题，采取的解法是模拟+dfs。首先讲一下模拟，扫雷游戏该如何模拟呢？分下列两种情况：
1.第一次点击的时候正好点击到了雷，这个时候就直接将这个位置的字母'M'改为'X'然后返回棋盘便可以了。
2.如果第一次点击没有点击到雷，那我们就可以进入到下一阶段的模拟。这个阶段的模拟首先得检查在这个位置的周围是否有雷？如果有，便将这个位置的值改为雷的个数。如果这个位置周围没有雷，那就将这个位置的值改为字符'B'然后递归这个位置周围的八个位置。
四，解题代码
class Solution {
public:int m,n;int dx[8] = {0,0,1,-1,1,1,-1,-1},dy[8] = {1,-1,0,0,1,-1,1,-1};//向量表示八个位置对应的下标vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {int x = click[0];int y = click[1];m = board.size();n = board[0].size();if(board[x][y] == 'M'){board[x][y] = 'X';return board;}dfs(x,y,board);return board;}void dfs(int i,int j,vector<vector<char>>&board){int count = 0;for(int k = 0;k<8;k++)//搜索周围的八个位置，查看是否有雷。{int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y] == 'M'){count++;}}if(count)//若有便将该位置上的值改为雷的个数{board[i][j] = '0'+count;}else{for(int k = 0;k<8;k++)//若无便搜索该位置周围的八个位置。{board[i][j] = 'B';int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y] == 'E'){dfs(x,y,board);}}}}
};