130. 被围绕的区域

题目描述

给定一个 m × n 的字符矩阵 board，其中每个格子都是：

"X"：被占领的区域。
"O"：开放区域。

如果一片由 "O" 组成的区域完全被 "X" 包围，就把这片区域中的所有 "O" 修改为 "X"。

格子只按照上、下、左、右四个方向相连。任何与矩阵边界上的 "O" 连通的区域都不会被包围，因此不能修改。

题目要求原地修改 board，不需要返回结果。

示例：

输入：
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" 位于边界上，必须保留。

1. 问题转换

直接判断每片 "O" 区域是否被包围，需要从区域内部出发搜索，再检查它能否触及边界。

更简单的做法是反过来思考：

不会被填充的 O
= 边界上的 O，以及所有与边界 O 四向连通的 O

因此可以先从所有边界 "O" 出发，做一次多源 BFS，将所有安全的 "O" 临时标记为 "#"。

搜索结束后：

仍然是 "O" 的格子无法与边界连通，一定被包围，改成 "X"。
被标记为 "#" 的格子与边界连通，不应被填充，恢复成 "O"。

这是一道典型的二维网格连通性 + 边界反向搜索问题。

2. 为什么从边界开始搜索

一片 "O" 区域只有两种情况：

与边界上的某个 "O" 连通，因此没有被完全包围。
不与任何边界 "O" 连通，因此四周都被 "X" 或矩阵内部边界阻隔，是需要填充的区域。

从边界出发可以一次找到第一类区域。剩余的 "O" 自动属于第二类，不需要逐个连通块判断是否触边。

这里搜索的是“需要保留的区域”，最后再统一处理其他格子。

3. 算法步骤

第一步：收集所有边界 `"O"`

矩阵边界包括：

第一列和最后一列。
第一行和最后一行。

遇到边界 "O" 时，将它立即标记为 "#" 并加入队列。

第二步：BFS 标记安全区域

不断从队列中取出一个格子，检查它的四个相邻位置。如果相邻位置仍为 "O"：

将它标记为 "#"。
将它加入队列，继续向外扩展。

必须在入队时立即标记，避免同一格子被多个邻居重复加入队列。

第三步：统一修改矩阵

再次遍历整个矩阵：

O -> X   无法连接边界，被包围
# -> O   能够连接边界，恢复原值
X -> X   保持不变

4. 示例推演

初始矩阵：

X X X X
X O O X
X X O X
X O X X

边界上只有 (3, 1) 是 "O"。从所有边界开始标记：

X X X X
X O O X
X X O X
X # X X

它没有相邻的 "O"，BFS 结束。中间三个 "O" 没有被标记，说明它们无法到达边界。

最终转换：

X X X X       X X X X
X O O X       X X X X
X X O X  ->   X X X X
X # X X       X O X X

5. BFS 代码实现

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

  const rows = board.length;
  const columns = board[0].length;
  const queue = [];
  let head = 0;

  const enqueueIfOpen = (row, column) => {
    if (board[row][column] !== "O") {
      return;
    }

    board[row][column] = "#";
    queue.push([row, column]);
  };

  // 第一列和最后一列。
  for (let row = 0; row < rows; row++) {
    enqueueIfOpen(row, 0);
    enqueueIfOpen(row, columns - 1);
  }

  // 第一行和最后一行。
  for (let column = 0; column < columns; column++) {
    enqueueIfOpen(0, column);
    enqueueIfOpen(rows - 1, column);
  }

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  while (head < queue.length) {
    const [row, column] = queue[head++];

    for (const [rowOffset, columnOffset] of directions) {
      const nextRow = row + rowOffset;
      const nextColumn = column + columnOffset;
      const isInBoard =
        nextRow >= 0 &&
        nextRow < rows &&
        nextColumn >= 0 &&
        nextColumn < columns;

      if (isInBoard && board[nextRow][nextColumn] === "O") {
        board[nextRow][nextColumn] = "#";
        queue.push([nextRow, nextColumn]);
      }
    }
  }

  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (board[row][column] === "O") {
        board[row][column] = "X";
      } else if (board[row][column] === "#") {
        board[row][column] = "O";
      }
    }
  }
};

队列使用 head 指针读取，而不是调用 shift()。JavaScript 数组的 shift() 可能需要移动后续元素，在队列很大时会增加不必要的开销。

6. 正确性说明

被标记为 `"#"` 的格子一定不能被填充

每个 "#" 要么原本就是边界 "O"，要么通过一条只包含 "O" 的路径与已标记格子相邻。因此，每个 "#" 都与某个边界 "O" 连通，不可能被 "X" 完全包围。

搜索后剩余的 `"O"` 一定应该被填充

如果某个剩余 "O" 能与边界连通，那么从对应边界 "O" 开始的 BFS 一定能够沿这条连通路径访问它，并把它标记为 "#"。这与它仍为 "O" 矛盾。

所以，剩余 "O" 都无法连接边界，属于被围绕的区域，应该修改为 "X"。

因此，最后一次遍历恰好填充所有被围绕区域，同时保留所有边界连通区域。

7. 复杂度分析

设矩阵大小为 m × n：

时间复杂度：O(m × n)。每个格子最多入队一次，最终转换还会遍历一次矩阵。
空间复杂度：O(m × n)。最坏情况下所有格子都是与边界连通的 "O"，队列会保存所有坐标。

临时字符 "#" 复用了原矩阵作为访问标记，因此不需要额外的 visited 矩阵。

8. DFS 实现

也可以从边界使用 DFS 标记安全区域：

var solve = function (board) {
  if (board.length === 0 || board[0].length === 0) {
    return;
  }

  const rows = board.length;
  const columns = board[0].length;

  const dfs = (row, column) => {
    const isOutOfBoard =
      row < 0 || row >= rows || column < 0 || column >= columns;

    if (isOutOfBoard || board[row][column] !== "O") {
      return;
    }

    board[row][column] = "#";
    dfs(row + 1, column);
    dfs(row - 1, column);
    dfs(row, column + 1);
    dfs(row, column - 1);
  };

  for (let row = 0; row < rows; row++) {
    dfs(row, 0);
    dfs(row, columns - 1);
  }

  for (let column = 0; column < columns; column++) {
    dfs(0, column);
    dfs(rows - 1, column);
  }

  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (board[row][column] === "O") {
        board[row][column] = "X";
      } else if (board[row][column] === "#") {
        board[row][column] = "O";
      }
    }
  }
};

BFS 和 DFS 的渐进复杂度相同。递归 DFS 更短，但当连通区域很大时，JavaScript 可能因递归层数过深而栈溢出，因此主实现使用显式队列的 BFS 更稳妥。

9. 边界条件与易错点

边界条件：

空矩阵无需处理。
单行或单列矩阵中的所有 "O" 都位于边界，不会被填充。
整张矩阵都是 "X" 时不发生变化。
整张矩阵都是 "O" 时，所有格子都与边界连通，不发生变化。
对角线相邻不算连通。

易错点：

不要一遇到 "O" 就改成 "X"，必须先保护所有与边界连通的区域。
四条边都要作为搜索起点，不能只检查第一行和第一列。
格子加入队列时就要标记，否则可能被多个邻居重复入队。
临时标记不能与原有字符冲突，处理结束后必须恢复为 "O"。
题目要求原地修改，不需要返回新矩阵。
右边界下标是 columns - 1，下边界下标是 rows - 1。

10. 常见错误思路

从每个内部 `"O"` 分别搜索边界

如果不记录已经处理的连通块，同一大片区域可能被重复搜索，最坏会退化到高于 O(m × n) 的复杂度。即使增加访问标记，也需要额外记录整个连通块，确认触边后再决定是否填充，实现更复杂。

先把所有内部 `"O"` 改成 `"X"`

内部格子虽然不在边界上，但可能通过其他 "O" 与边界相连。是否被包围取决于整个连通分量，而不是单个格子的位置。

只保护边界格子

不仅边界上的 "O" 安全，所有与它们四向连通的内部 "O" 也安全，必须通过 BFS 或 DFS 完整扩展。

11. 面试追问

这道题与「岛屿数量」有什么联系？

两题都把二维矩阵看作隐式图，每个格子是节点，四向相邻关系是边。「岛屿数量」需要扫描并统计所有连通分量；本题只关心哪些 "O" 连通分量与边界相交，因此从边界反向搜索更直接。

能否使用并查集？

可以。建立一个虚拟边界节点，把所有边界 "O" 与它合并，再合并相邻的 "O"。最后，不与虚拟节点连通的 "O" 都需要改为 "X"。不过并查集需要额外数组，代码也比 BFS/DFS 更复杂。

如果不能修改输入怎么办？

使用 m × n 的布尔矩阵记录与边界连通的安全格子，最后根据访问状态生成新矩阵。时间复杂度不变，额外空间仍为 O(m × n)。

为什么这是多源 BFS？

所有边界 "O" 都是搜索源点。可以先把它们统一加入同一个队列，再共同向内部扩展；这相当于同时从多个起点执行 BFS。

12. 可迁移总结

本题的核心转换是：

直接寻找“被包围区域”较麻烦
  -> 先从边界寻找所有“不可能被包围的区域”
    -> 剩余区域就是答案

遇到二维网格中的边界逃逸、封闭区域或连通性问题时，可以优先思考：

哪些格子天然安全或天然不合法？
能否从边界进行多源 BFS/DFS？
能否先标记补集，再统一处理剩余格子？

类似思路还可以用于统计封闭岛屿、飞地数量、边界着色以及判断区域能否逃逸等问题。

#130. 被围绕的区域

#题目描述

#1. 问题转换

#2. 为什么从边界开始搜索

#3. 算法步骤

#第一步：收集所有边界 "O"

#第二步：BFS 标记安全区域

#第三步：统一修改矩阵

#4. 示例推演

#5. BFS 代码实现

#6. 正确性说明

#被标记为 "#" 的格子一定不能被填充

#搜索后剩余的 "O" 一定应该被填充

#7. 复杂度分析

#8. DFS 实现

#9. 边界条件与易错点

#10. 常见错误思路

#从每个内部 "O" 分别搜索边界

#先把所有内部 "O" 改成 "X"

#只保护边界格子

#11. 面试追问

#这道题与「岛屿数量」有什么联系？

#能否使用并查集？

#如果不能修改输入怎么办？

#为什么这是多源 BFS？

#12. 可迁移总结