被围绕的区域

题目

给你一个 m x n 的矩阵 board , 由若干字符 'X' 和 'O' 组成, 捕获所有被围绕的区域:

• 连接: 一个单元格与水平或垂直方向上相邻的单元格连接.
• 区域: 连接所有 'O' 的单元格来形成一个区域.
• 围绕: 如果您可以用 'X' 单元格 连接这个区域, 并且区域中没有任何单元格位于 board 边缘, 则该区域被 'X' 单元格围绕.

通过原地将输入矩阵中的所有 'O' 替换为 'X' 来捕获被围绕的区域. 你不需要返回任何值.

提示:

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

示例

示例 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"]]

解释:

在上图中, 底部的区域没有被捕获, 因为它在 board 的边缘并且不能被围绕.

示例 2:

输入: board = [["X"]

输出: [["X"]]

题解

被围绕的区间不会存在于边界上, 换句话说, 任何边界上的 'O' 都不会被填充为 'X'. 而任何不在边界上, 或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'. 如果两个元素在水平或垂直方向相邻, 则称它们是相连的.

因此我们检查 board 四个边的每个元素: 如果遇到 'O', 意味着该处不应被填充为 'X', 暂且用 '#' 替代; 那么继续从该处上下左右探索, 与之接触的 'O' 都不应被填充为 'X', 因此都用 '#' 替代.

最后我们遍历整个 board 的每个元素, 如果还是 'O', 意味着其被"捕获"了, 将其变成 'X'; 而对于那些用 '#' 替代的, 则还原成 'O'.

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
  const m = board.length
  const n = board[0].length

  const dfs = (i, j) => {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== `'O'`) return

    board[i][j] = `'#'`
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j + 1)
    dfs(i, j - 1)
  }

  for (let i = 0; i < m; i++) {
    dfs(i, 0)
    dfs(i, n - 1)
  }

  for (let j = 0; j < n; j++) {
    dfs(0, j)
    dfs(m - 1, j)
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === `'O'`) {
        board[i][j] = `'X'`
      } else if (board[i][j] === `'#'`) {
        board[i][j] = `'O'`
      }
    }
  }
}