本文共 2686 字，大约阅读时间需要 8 分钟。

1. 题目

让我们一起来玩扫雷游戏！

给定一个代表游戏板的二维字符矩阵。

现在给出在所有未挖出的方块中（‘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
   
    
     > updateBoard(vector
     
      
       >& board, vector
       
        & click) {
       	if(board[click[0]][click[1]] == 'M')//点击的是地雷，直接标记X，结束    	{
       		board[click[0]][click[1]] = 'X';    		return board;    	}    	vector
        
         
          > 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
          
           
            > q; q.push(click); vector
            
             
              > visited(m,vector
              
               (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
               
                =0 && y
                
                 =0 && x
                 
                  =0 && y
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

2.2 DFS

class Solution {
       vector
   
    
     > dir = {
   {
   1,0},{
   0,1},{
   -1,0},{
   0,-1},{
   1,1},{
   -1,-1},{
   1,-1},{
   -1,1}};    int m,n;public:    vector
     
      
       > updateBoard(vector
       
        
         >& board, vector
         
          & click) { if(board[click[0]][click[1]] == 'M') { board[click[0]][click[1]] = 'X'; return board; } m = board.size(), n = board[0].size(); vector
          
           
            > visited(m,vector
            
             (n,false)); visited[click[0]][click[1]] = true; dfs(board,click[0],click[1],visited); return board; } void dfs(vector
             
              
               >& board, int i, int j, vector
               
                
                 >& 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
                 
                  =0 && y
                  
                   =0 && x
                   
                    =0 && y
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/105960312 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！