LeetCode 130. 被围绕的区域
字数 1734 2025-10-31 08:19:17

LeetCode 130. 被围绕的区域

题目描述

给你一个 m x n 的矩阵 board，由字符 'X' 和 'O' 组成。你需要捕获所有被 'X' 围绕的区域。捕获一个区域意味着，将该区域中所有的 'O' 用 'X' 填充。

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个单元格相邻（上下左右四个方向），则它们是“相连”的。

解题过程

这个问题的核心在于识别哪些 'O' 是“安全”的，即它们要么在边界上，要么与边界上的 'O' 连通。这些“安全”的 'O' 不应该被变成 'X'。而所有其他的 'O'（即被 'X' 完全包围的）则需要被捕获（变成 'X'）。

直接找出所有被包围的区域比较困难。一个更巧妙的“逆向思维”是：我们先找出所有“安全”的 'O'，那么剩下的 'O' 就是需要被捕获的。

循序渐进步骤：

  1. 预处理：标记边界连通区域

    • 我们的目标是找到所有与边界相连的 'O'（即“安全”的 'O'）。我们可以从边界上的每一个 'O' 开始，进行深度优先搜索（DFS）或广度优先搜索（BFS），去寻找所有与它们连通的 'O'。
    • 为了不破坏原始数据，我们用一个特殊的临时标记（例如 'A'）来标识这些“安全”的 'O'。
    • 具体操作：
      • 遍历矩阵的四条边（第一行、最后一行、第一列、最后一列）。
      • 如果遇到一个 'O'，就从这个位置开始进行 DFS/BFS，将所有与之连通的 'O' 都标记为 'A'。

  2. 处理剩余区域

    • 经过第一步后，矩阵中所有“安全”的 'O' 都被标记为了 'A'。
    • 现在，矩阵中剩下的 'O' 就是那些不与边界相连、被 'X' 包围的 'O'，也就是我们需要捕获的目标。
    • 具体操作：
      • 遍历整个矩阵。
      • 对于每一个单元格：
        • 如果它是 'O'，说明它是被包围的，将其改为 'X'。
        • 如果它是 'A'，说明它是“安全”的，将其恢复为 'O'。

  3. 算法选择：DFS 实现

    • 我们使用深度优先搜索来进行第一步的标记工作。DFS 会从一个边界上的 'O' 开始，递归地访问其上下左右四个方向的相邻单元格。如果是 'O'，就继续递归标记。

详细步骤演示（结合代码逻辑）：

假设我们有一个矩阵：

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

  1. 标记边界连通区域（使用 DFS）：

    • 我们遍历四条边。
    • 在第一条边（第一行）上，没有 'O'。
    • 在最后一行（第四行）上，有一个 'O' 在位置 (3,1)（行列索引从0开始）。
    • 我们从 (3,1) 开始 DFS：
      • 标记 (3,1) 为 'A'。
      • 检查其四个邻居：上 (2,1) 是 'X'，下越界，左 (3,0) 是 'X'，右 (3,2) 是 'X'。DFS 结束。
    • 遍历第一列和最后一列，没有发现其他边界上的 'O'。
    • 此时，只有 (3,1) 被标记为 'A'。矩阵变为：
    X X X X
X O O X
X X O X
X A X X  // (3,1) 的 'O' 被标记为 'A'
    • 注意：在这个例子中，位于 (1,1), (1,2), (2,2) 的 'O' 并没有与边界上的 'O'（即 (3,1)）连通，所以它们没有被标记为 'A'。

  2. 处理剩余区域：

    • 我们遍历整个矩阵：
      • (1,1) 是 'O' -> 捕获，变为 'X'。
      • (1,2) 是 'O' -> 捕获，变为 'X'。
      • (2,2) 是 'O' -> 捕获，变为 'X'。
      • (3,1) 是 'A' -> 恢复为 'O'。
    • 最终矩阵变为：
    X X X X
X X X X
X X X X
X O X X

    这正是期望的结果。中间的 'O' 被捕获了，而左下角的 'O' 因为与边界相连得以保留。

关键思路总结：
这个解法巧妙地利用了“逆向思维”和“标记法”。核心洞察是直接寻找被包围的区域很困难，但寻找“不被包围”的区域（即与边界连通的区域）则可以通过标准的图搜索算法（DFS/BFS）轻松实现。通过先标记出所有“安全”的点，剩下的目标点就一目了然了。

LeetCode 130. 被围绕的区域 题目描述 给你一个 m x n 的矩阵 board ，由字符 'X' 和 'O' 组成。你需要捕获所有被 'X' 围绕的区域。捕获一个区域意味着，将该区域中所有的 'O' 用 'X' 填充。 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X' 。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X' 。如果两个单元格相邻（上下左右四个方向），则它们是“相连”的。 解题过程 这个问题的核心在于识别哪些 'O' 是“安全”的，即它们要么在边界上，要么与边界上的 'O' 连通。这些“安全”的 'O' 不应该被变成 'X' 。而所有其他的 'O' （即被 'X' 完全包围的）则需要被捕获（变成 'X' ）。 直接找出所有被包围的区域比较困难。一个更巧妙的“逆向思维”是： 我们先找出所有“安全”的 'O' ，那么剩下的 'O' 就是需要被捕获的。 循序渐进步骤： 预处理：标记边界连通区域 我们的目标是找到所有与边界相连的 'O' （即“安全”的 'O' ）。我们可以从边界上的每一个 'O' 开始，进行深度优先搜索（DFS）或广度优先搜索（BFS），去寻找所有与它们连通的 'O' 。 为了不破坏原始数据，我们用一个特殊的临时标记（例如 'A' ）来标识这些“安全”的 'O' 。 具体操作： 遍历矩阵的四条边（第一行、最后一行、第一列、最后一列）。 如果遇到一个 'O' ，就从这个位置开始进行 DFS/BFS，将所有与之连通的 'O' 都标记为 'A' 。 处理剩余区域 经过第一步后，矩阵中所有“安全”的 'O' 都被标记为了 'A' 。 现在，矩阵中剩下的 'O' 就是那些不与边界相连、被 'X' 包围的 'O' ，也就是我们需要捕获的目标。 具体操作： 遍历整个矩阵。 对于每一个单元格： 如果它是 'O' ，说明它是被包围的，将其改为 'X' 。 如果它是 'A' ，说明它是“安全”的，将其恢复为 'O' 。 算法选择：DFS 实现 我们使用深度优先搜索来进行第一步的标记工作。DFS 会从一个边界上的 'O' 开始，递归地访问其上下左右四个方向的相邻单元格。如果是 'O' ，就继续递归标记。 详细步骤演示（结合代码逻辑）： 假设我们有一个矩阵： 标记边界连通区域（使用 DFS）： 我们遍历四条边。 在第一条边（第一行）上，没有 'O' 。 在最后一行（第四行）上，有一个 'O' 在位置 (3,1) （行列索引从0开始）。 我们从 (3,1) 开始 DFS： 标记 (3,1) 为 'A' 。 检查其四个邻居：上 (2,1) 是 'X' ，下越界，左 (3,0) 是 'X' ，右 (3,2) 是 'X' 。DFS 结束。 遍历第一列和最后一列，没有发现其他边界上的 'O' 。 此时，只有 (3,1) 被标记为 'A' 。矩阵变为： 注意：在这个例子中，位于 (1,1) , (1,2) , (2,2) 的 'O' 并没有与边界上的 'O' （即 (3,1) ）连通，所以它们没有被标记为 'A' 。 处理剩余区域： 我们遍历整个矩阵： (1,1) 是 'O' -> 捕获，变为 'X' 。 (1,2) 是 'O' -> 捕获，变为 'X' 。 (2,2) 是 'O' -> 捕获，变为 'X' 。 (3,1) 是 'A' -> 恢复为 'O' 。 最终矩阵变为： 这正是期望的结果。中间的 'O' 被捕获了，而左下角的 'O' 因为与边界相连得以保留。 关键思路总结： 这个解法巧妙地利用了“逆向思维”和“标记法”。核心洞察是直接寻找被包围的区域很困难，但寻找“不被包围”的区域（即与边界连通的区域）则可以通过标准的图搜索算法（DFS/BFS）轻松实现。通过先标记出所有“安全”的点，剩下的目标点就一目了然了。