文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 BFS
    • 2.2 DFS

1. 題目

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

給定一個代表游戲板的二維字符矩陣。
‘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')，這也意味著面板至少包含一個可點擊的方塊。 輸入面板不會是游戲結束的狀態（即有地雷已被挖出）。 簡單起見，未提及的規則在這個問題中可被忽略。 例如，當游戲結束時你不需要挖出所有地雷，考慮所有你可能贏得游戲或標記方塊的情況。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/minesweeper
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 BFS

class Solution { public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {if(board[click[0]][click[1]] == 'M')//點擊的是地雷，直接標記X，結束{board[click[0]][click[1]] = 'X';return board;}vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};int m = board.size(), n = board[0].size();int i, j, x, y, k, count;queue<vector<int>> q;q.push(click);vector<vector<bool>> visited(m,vector<bool>(n,false));//訪問標記visited[click[0]][click[1]] = true;while(!q.empty()){i = q.front()[0];j = q.front()[1];q.pop();count = 0;for(k = 0; k < 8; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M')count++;//8個方向有幾顆地雷}if(count == 0)//地雷為0，需要周圍的都加入隊列，去檢查是否繼續翻開{board[i][j] = 'B';//中間標記為Bfor(k = 0; k < 8; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && board[x][y]=='E'){q.push({x,y});visited[x][y] = true;}}}else{ //不為零，標記為數字board[i][j] = char('0'+count);}}return board;} };

2.2 DFS

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};int m,n; public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {if(board[click[0]][click[1]] == 'M'){board[click[0]][click[1]] = 'X';return board;}m = board.size(), n = board[0].size();vector<vector<bool>> visited(m,vector<bool>(n,false));visited[click[0]][click[1]] = true;dfs(board,click[0],click[1],visited);return board;}void dfs(vector<vector<char>>& board, int i, int j, vector<vector<bool>>& visited){int x, y, k, count = 0;for(k = 0; k < 8; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M')count++;//8個方向有幾顆地雷}if(count == 0)//地雷為0，需要周圍的都加入隊列，去檢查是否繼續翻開{board[i][j] = 'B';//中間標記為Bfor(k = 0; k < 8; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && board[x][y]=='E'){visited[x][y] = true;dfs(board,x,y,visited);}}}else{ //不為零，標記為數字board[i][j] = char('0'+count);}} };

總結

以上是生活随笔為你收集整理的LeetCode 529. 扫雷游戏（广度优先搜索BFS/深度优先搜索DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。