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

提示：

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

  解法一：回溯

function solve(board: string[][]): void {
  const xMap = [0, 0, 1, -1]
  const yMap = [1, -1, 0, 0]
  let m = board.length
  let n = board[0].length
  for(let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 这里需要注意要从边界开始计算不需要转换的区域
      const isBoundary =  i === 0 || i === m - 1 || j === 0 || j === n -1
      if (isBoundary && board[i][j] === "O") {
        recursion(i, 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"
      }
    }
  }
  function recursion(x: number, y :number) {
    if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] !== "O" ) {
      return
    }
    board[x][y] = "#"
    for (let i = 0; i < 4; i++) {
      recursion(x + xMap[i], y + yMap[i])
    }
  }
  return
};