LeetCode 130. 被围绕的区域
字数 945 2025-10-28 00:29:09

LeetCode 130. 被围绕的区域

题目描述
给你一个 m x n 的矩阵 board，由若干字符 'X' 和 'O' 组成。请你捕获所有被 'X' 围绕的区域，并将这些区域中所有的 'O' 用 'X' 填充。被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解题思路

  1. 问题分析：直接判断内部的 'O' 是否被 'X' 包围比较困难，但可以逆向思考：所有与边界相连的 'O' 都是安全的，不会被填充；其余内部的 'O' 则需要被填充。
  2. 关键思路：从边界上的每一个 'O' 出发，通过深度优先搜索（DFS）或广度优先搜索（BFS）标记所有与之相连的 'O'（例如临时改为 '#'），这些是安全区域。
  3. 处理步骤：
    • 遍历四条边界上的点，若遇到 'O'，则启动 DFS/BFS 标记相连区域。
    • 遍历整个矩阵，将标记为 '#' 的恢复为 'O'，未标记的 'O' 改为 'X'。

详细步骤

  1. 边界遍历：
    • 检查第一行和最后一行（上下边界），对每个 'O' 执行标记操作。
    • 检查第一列和最后一列（左右边界），对每个 'O' 执行标记操作。
  2. 标记安全区域（以 DFS 为例）：
    • 递归访问当前点的上下左右四个方向，若为 'O' 则标记为 '#' 并继续递归。
    • 注意边界条件（坐标不越界）。
  3. 最终转换：
    • 遍历整个矩阵：
      • 遇到 '#' 说明是安全区域，恢复为 'O'。
      • 遇到 'O' 说明是未被标记的内部区域，改为 'X'。

示例演示
以矩阵

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

为例：

  1. 标记边界上的 'O'（第三行最后一列的 'O' 在边界上未被包围，但本例中边界无 'O'，需注意实际边界是否存在 'O'）。
  2. 标记后，内部未被连接的 'O' 会被填充，最终结果需根据实际边界情况调整。

总结
通过从边界反向标记的方式，避免了直接判断内部区域的复杂性，确保了算法的高效性（时间复杂度 O(mn)）。

LeetCode 130. 被围绕的区域 题目描述 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成。请你捕获所有被 'X' 围绕的区域，并将这些区域中所有的 'O' 用 'X' 填充。被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X' 。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X' 。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。 解题思路 问题分析 ：直接判断内部的 'O' 是否被 'X' 包围比较困难，但可以逆向思考：所有与边界相连的 'O' 都是安全的，不会被填充；其余内部的 'O' 则需要被填充。 关键思路 ：从边界上的每一个 'O' 出发，通过深度优先搜索（DFS）或广度优先搜索（BFS）标记所有与之相连的 'O' （例如临时改为 '#' ），这些是安全区域。 处理步骤 ： 遍历四条边界上的点，若遇到 'O' ，则启动 DFS/BFS 标记相连区域。 遍历整个矩阵，将标记为 '#' 的恢复为 'O' ，未标记的 'O' 改为 'X' 。 详细步骤 边界遍历 ： 检查第一行和最后一行（上下边界），对每个 'O' 执行标记操作。 检查第一列和最后一列（左右边界），对每个 'O' 执行标记操作。 标记安全区域 （以 DFS 为例）： 递归访问当前点的上下左右四个方向，若为 'O' 则标记为 '#' 并继续递归。 注意边界条件（坐标不越界）。 最终转换 ： 遍历整个矩阵： 遇到 '#' 说明是安全区域，恢复为 'O' 。 遇到 'O' 说明是未被标记的内部区域，改为 'X' 。 示例演示 以矩阵 为例： 标记边界上的 'O' （第三行最后一列的 'O' 在边界上未被包围，但本例中边界无 'O' ，需注意实际边界是否存在 'O' ）。 标记后，内部未被连接的 'O' 会被填充，最终结果需根据实际边界情况调整。 总结 通过从边界反向标记的方式，避免了直接判断内部区域的复杂性，确保了算法的高效性（时间复杂度 O(mn)）。