目錄

一，題目

二，題目接口

三，解題思路

四，解題代碼

---

一，題目

讓我們一起來玩掃雷游戲！

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

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

給你一個整數數組?click?，其中?click = [clickr, clickc]?表示在所有?未挖出的?方塊（'M'?或者?'E'）中的下一個點擊位置（clickr?是行下標，clickc?是列下標）。

根據以下規(guī)則，返回相應位置被點擊后對應的盤面：

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

二，題目接口

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);}}}}
};

?

?

?