[130] 被围绕的区域

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

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

提示：

board[i][j] 为 'X' 或 'O'

这道题的解题思路与 [1254] 统计封闭岛屿的数目 几乎一致，也是岛屿问题的一个变种。

这道题中，因为要使用原地算法，不能直接淹没边缘的岛屿，我们需要多维护一个访问数组来辅助判断此时访问的陆地是否需要淹没。

（当然，我们也可以不增加访问数组，在原地数组中，当发现为边缘的岛屿时，将这种岛屿标记为P，最后再遍历整个数组，将P复原为O，也能实现同样的效果）

function solve(board: string[][]): void {
  const width = board[0].length;
  const height = board.length;
  const visited: boolean[][] = Array(height)
    .fill(0)
    .map(x => Array(width).fill(false));

  for (let i = 0; i < height; i++) {
    dfs(i, 0, false);
    dfs(i, width - 1, false);
  }
  for (let j = 0; j < width; j++) {
    dfs(0, j, false);
    dfs(height - 1, j, false);
  }

  for (let i = 1; i < height - 1; i++) {
    for (let j = 1; j < width - 1; j++) {
      if (!visited[i][j] && board[i][j] === 'O') {
        dfs(i, j, true);
      }
    }
  }

  function dfs(i: number, j: number, needFill: boolean) {
    if (i < 0 || i >= height || j < 0 || j > width) return;
    if (visited[i][j] || board[i][j] === 'X') return;

    visited[i][j] = true;
    if (needFill) board[i][j] = 'X';

    dfs(i - 1, j, needFill);
    dfs(i + 1, j, needFill);
    dfs(i, j - 1, needFill);
    dfs(i, j + 1, needFill);
  }
}