您是小站的第 27972 位访客,欢迎~

您现在的位置是: 网站首页 > 程序设计  > leetcode 

leetcode-0130. 被围绕的区域

2021年9月18日 23:53 139人围观

简介给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

    给你一个 m x n 的矩阵 board ,由若干字符 'X''O' ,找到所有被'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

    示例1:

    https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg

     
    输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] 
    输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] 
    解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。 
    

    示例 2:

    输入:board = [["X"]] 
    输出:[["X"]] 
    

    提示:

    • m == board.length
    • n == board[i].length
    • 1 <= m, n <= 200
    • board[i][j] 为 'X' 或 'O'

    这道题有两种思路:

    1. 判断所有的O,看其是否能走到边界上
    2. 从边界上的O出发,所有与之相连的O都不能替换

    3. 解法一:

    
    
    • 解法二:

    为了提高效率,我们优化掉状态量visit,对于访问过的结点,将其标记成#,由于只从边界的O出发,那么所有能走到的O都不能替换(因为他们没有被包围)。

      class Solution { 
      public: 
          void dfs(int x, int y, vector<vector<char>> &board) { 
              int M = board.size(); 
              int N = board[0].size(); 
              board[x][y] = '#'; 
    
              int step[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; 
    
              for (int k = 0; k < 4; k++) { 
                  int i = x + step[k][0]; 
                  int j = y + step[k][1]; 
    
                  if (i >= M || j >= N || i < 0 || j < 0) { //越界了 
                      continue ; 
                  } 
                  if (board[i][j] == 'O') { // 只要是与边界相连的O,都不能替换 
                      dfs(i, j, board);  
                  } 
              } 
          } 
          void solve(vector<vector<char>>& board) { 
              if (board.size() == 0) { 
                  return; 
              } 
    
              int M = board.size(); 
              int N = board[0].size(); 
              if (M <=2 || N <= 2) { 
                  return; 
              } 
              vector<vector<bool>> visit(M, vector<bool>(N, false)); 
              vector<pair<int, int>> result; 
              for (int i = 0; i  < M; i++) { 
                  if (board[i][0] == 'O' ) { 
                      dfs(i, 0, board); 
                  } 
                  if (board[i][N - 1] == 'O') { 
                      dfs(i, N - 1, board); 
                  } 
              } 
              for (int i = 0; i < N; i++) { 
                  if (board[0][i] == 'O') { 
                     dfs(0, i,  board); 
                  } 
                  if (board[M - 1][i] == 'O') { 
                      dfs(M - 1, i, board); 
                  } 
              } 
    
              for (int i = 0; i < M; i++ ) { 
                  for (int j = 0; j < N; j++) { 
                      if (board[i][j] == '#') { 
                          board[i][j] = 'O'; 
                      } 
                      else if (board[i][j] == 'O'){ 
                          board[i][j] = 'X'; 
                      } 
                  } 
              } 
          } 
      };