C++刷LeetCode（529. 扫雷游戏）【深度优先搜索】

糖逗

题目描述：

1. 
   
2. 让我们一起来玩扫雷游戏！
   
3. 
   
4. 给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
   
5. 
   
6. 现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
   
7. 
   
8. 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
   
9. 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
   
10. 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
    
11. 如果在此次点击中，若无更多方块可被揭露，则返回面板。
    
12. 
    
13. 
    
14. 示例 1：
    
15. 
    
16. 输入:
    
17. 
    
18. [['E', 'E', 'E', 'E', 'E'],
    
19. ['E', 'E', 'M', 'E', 'E'],
    
20. ['E', 'E', 'E', 'E', 'E'],
    
21. ['E', 'E', 'E', 'E', 'E']]
    
22. 
    
23. Click : [3,0]
    
24. 
    
25. 输出:
    
26. 
    
27. [['B', '1', 'E', '1', 'B'],
    
28. ['B', '1', 'M', '1', 'B'],
    
29. ['B', '1', '1', '1', 'B'],
    
30. ['B', 'B', 'B', 'B', 'B']]
    
31. 
    
32. 解释:
    
33. 
    
34. 示例 2：
    
35. 
    
36. 输入:
    
37. 
    
38. [['B', '1', 'E', '1', 'B'],
    
39. ['B', '1', 'M', '1', 'B'],
    
40. ['B', '1', '1', '1', 'B'],
    
41. ['B', 'B', 'B', 'B', 'B']]
    
42. 
    
43. Click : [1,2]
    
44. 
    
45. 输出:
    
46. 
    
47. [['B', '1', 'E', '1', 'B'],
    
48. ['B', '1', 'X', '1', 'B'],
    
49. ['B', '1', '1', '1', 'B'],
    
50. ['B', 'B', 'B', 'B', 'B']]
    
51. 
    
52. 解释:
    
53. 
    
54. 
    
55. 
    
56. 注意：
    
57. 
    
58. 输入矩阵的宽和高的范围为 [1,50]。
    
59. 点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。
    
60. 输入面板不会是游戏结束的状态（即有地雷已被挖出）。
    
61. 简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。

复制代码

1. class Solution {
   
2. public:
   
3.     bool valid(vector<vector<char> >&board, int temp1, int temp2, int & count){
   
4.         int len1 = board.size(), len2 = board[0].size();
   
5.         if(board[temp1][temp2] == 'E'){
   
6.             if(temp1+1 < len1 && board[temp1+1][temp2] == 'M')count++;
   
7.             if(temp1-1 >= 0 && board[temp1-1][temp2] == 'M')count++;
   
8.             if(temp2+1 < len2 && board[temp1][temp2+1] == 'M')count++;
   
9.             if(temp2-1 >= 0 && board[temp1][temp2-1] == 'M')count++;
   
10.             if(temp1-1 >= 0 && temp2-1 >= 0 && board[temp1-1][temp2-1] == 'M')count++;
    
11.             if(temp1-1 >= 0 && temp2+1 < len2 && board[temp1-1][temp2+1] == 'M')count++;
    
12.             if(temp1+1 < len1 && temp2-1 >= 0 && board[temp1+1][temp2-1] == 'M')count++;
    
13.             if(temp1+ 1 < len1 && temp2+1 < len2 && board[temp1+1][temp2+1] == 'M')count++;
    
14.         }
    
15.         if(count > 0)return false;
    
16.         return true;
    
17.     }
    
18.     void dfs(vector<vector<char> >&board, int temp1, int temp2){
    
19.         if(temp1 >= board.size() || temp1 < 0 || temp2 >= board[0].size() || temp2 < 0 || board[temp1][temp2] != 'E')return;
    
20.         int count = 0;
    
21.         bool flag = valid(board, temp1, temp2, count);
    
22.         if(flag == true){
    
23.             board[temp1][temp2] = 'B';
    
24.             dfs(board, temp1 + 1, temp2);
    
25.             dfs(board, temp1 - 1, temp2);
    
26.             dfs(board, temp1, temp2 + 1);
    
27.             dfs(board, temp1, temp2 - 1);
    
28.             dfs(board, temp1 + 1, temp2 + 1);//注意可以8个方向递归
    
29.             dfs(board, temp1 - 1, temp2 - 1);
    
30.             dfs(board, temp1 - 1, temp2 + 1);
    
31.             dfs(board, temp1 + 1, temp2 - 1);
    
32.         }else{
    
33.             board[temp1][temp2] = count + '0';
    
34.         }
    
35. 
    
36.     }
    
37.     vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
    
38.         int temp1 = click[0], temp2 = click[1];
    
39.         int count = 0;
    
40.         bool flag = valid(board, temp1, temp2, count);
    
41.         if(board[temp1][temp2] == 'M'){
    
42.             board[temp1][temp2] = 'X';
    
43.         }else if(board[temp1][temp2] != 'E'){
    
44.             return board;
    
45.         }else if(flag == true){
    
46.             dfs(board, temp1, temp2);
    
47.         }else if(flag == false){
    
48.             board[temp1][temp2] = count + '0';
    
49.         }
    
50.         return board;
    
51.     }
    
52. };

复制代码