题目

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

示例 1：
[中等] 130. 被围绕的区域 - 图1

输入：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"]]

解答 & 代码

本题思路基本同：[中等] 1254. 统计封闭岛屿的数目

遍历上、下、左、右四个边界，以每个边界上的 'O' 为起点，DFS 将其本身以及与之相邻的 'O' 都填充为 'T'

因为这部分并没有被围绕，所以需要修改，以防止下一步被填充为 'X'

遍历矩阵，对每个位置，将 'O' 填充为 'X'，将 'T' 重新填充为 'O'

注意只改变这个位置本身，不用做 DFS！

class Solution {
private:
  // 深度优先搜索，从位置 (row, col) 开始，将与之相邻的 ori 字符都填充为 target 字符
  void dfs(vector<vector<char>>& board, int row, int col, char ori, char target)
  {
      int rows = board.size();
      int cols = board[0].size();
      if(row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != ori)
          return;

      board[row][col] = target;
      dfs(board, row + 1, col, ori, target);
      dfs(board, row - 1, col, ori, target);
      dfs(board, row, col + 1, ori, target);
      dfs(board, row, col - 1, ori, target);
  }
public:
  void solve(vector<vector<char>>& board) {
      int rows = board.size();
      int cols = board[0].size();
      // 1. DFS 将靠上、下、左、右边界的 'O' 及与之相邻的 'O' 都填充为 'T'
      for(int j = 0; j < cols; ++j)
      {
          if(board[0][j] == 'O')
              dfs(board, 0, j, 'O', 'T');            // 上边界
          if(board[rows - 1][j] == 'O')
              dfs(board, rows - 1, j, 'O', 'T');    // 下边界
      }
      for(int i = 0; i < rows; ++i)
      {
          if(board[i][0] == 'O')
              dfs(board, i, 0, 'O', 'T');            // 左边界
          if(board[i][cols - 1] == 'O')
              dfs(board, i, cols - 1, 'O', 'T');    // 右边界
      }

      // 2. 遍历矩阵，对每个位置，将 'O' 填充为 'X'，将 'T' 重新填充为 'O'
      // 注意只改变该位置本身的值，不用 DFS
      for(int i = 0; i < rows; ++i)
      {
          for(int j = 0; j < cols; ++j)
          {
              if(board[i][j] == 'O')
                  board[i][j] = 'X';
              else if(board[i][j] == 'T')
                  board[i][j] = 'O';
          }
      }
  }
};

复杂度分析：设 m 行 n 列

时间复杂度 O(mn)：
空间复杂度 O(mn)：最坏情况下的递归深度

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 63.68% 的用户
内存消耗：9.7 MB, 在所有 C++ 提交中击败了 60.27% 的用户