目錄

一，題目

二，題目接口

三，解題思路

四，解題代碼

---

一，題目

讓我們一起來(lái)玩掃雷游戲！

給你一個(gè)大小為?m x n?二維字符矩陣?board?，表示掃雷游戲的盤面，其中：

• 'M'?代表一個(gè)?未挖出的?地雷，
• 'E'?代表一個(gè)?未挖出的?空方塊，
• 'B'?代表沒有相鄰（上，下，左，右，和所有4個(gè)對(duì)角線）地雷的?已挖出的?空白方塊，
• 數(shù)字（'1'?到?'8'）表示有多少地雷與這塊?已挖出的?方塊相鄰，
• 'X'?則表示一個(gè)?已挖出的?地雷。

給你一個(gè)整數(shù)數(shù)組?click?，其中?click = [clickr, clickc]?表示在所有?未挖出的?方塊（'M'?或者?'E'）中的下一個(gè)點(diǎn)擊位置（clickr?是行下標(biāo)，clickc?是列下標(biāo)）。

根據(jù)以下規(guī)則，返回相應(yīng)位置被點(diǎn)擊后對(duì)應(yīng)的盤面：

1. 如果一個(gè)地雷（'M'）被挖出，游戲就結(jié)束了- 把它改為?'X'?。
2. 如果一個(gè)?沒有相鄰地雷?的空方塊（'E'）被挖出，修改它為（'B'），并且所有和其相鄰的?未挖出?方塊都應(yīng)該被遞歸地揭露。
3. 如果一個(gè)?至少與一個(gè)地雷相鄰?的空方塊（'E'）被挖出，修改它為數(shù)字（'1'?到?'8'?），表示相鄰地雷的數(shù)量。
4. 如果在此次點(diǎn)擊中，若無(wú)更多方塊可被揭露，則返回盤面。

二，題目接口

class Solution {
public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {}
};

三，解題思路

對(duì)于這道題，采取的解法是模擬+dfs。首先講一下模擬，掃雷游戲該如何模擬呢？分下列兩種情況：

1.第一次點(diǎn)擊的時(shí)候正好點(diǎn)擊到了雷，這個(gè)時(shí)候就直接將這個(gè)位置的字母'M'改為'X'然后返回棋盤便可以了。

2.如果第一次點(diǎn)擊沒有點(diǎn)擊到雷，那我們就可以進(jìn)入到下一階段的模擬。這個(gè)階段的模擬首先得檢查在這個(gè)位置的周圍是否有雷？如果有，便將這個(gè)位置的值改為雷的個(gè)數(shù)。如果這個(gè)位置周圍沒有雷，那就將這個(gè)位置的值改為字符'B'然后遞歸這個(gè)位置周圍的八個(gè)位置。

四，解題代碼

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};//向量表示八個(gè)位置對(duì)應(yīng)的下標(biāo)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++)//搜索周圍的八個(gè)位置，查看是否有雷。{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)//若有便將該位置上的值改為雷的個(gè)數(shù){board[i][j] = '0'+count;}else{for(int k = 0;k<8;k++)//若無(wú)便搜索該位置周圍的八個(gè)位置。{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);}}}}
};

?

?

?