被围绕的区域-LeetCode

130. 被围绕的区域 - Surrounded Regions

🎯 问题描述（来源于LeetCode）

描述：
给你一个 m x n 的矩阵 board，由字符 'X' 和 'O' 组成。
如果所有与边界连通的 'O' 区域称为「不被围绕的区域」，而完全被 'X' 包围的 'O' 区域（即无法通过上下左右走到边界）需要被翻转成 'X'。
请原地修改矩阵，将所有被 'X' 包围的 'O' 翻转为 'X'。

说明：

• 边界上的 'O' 不会被翻转。
• 与边界上的 'O' 连通的 'O' 也不会被翻转。

示例：

• 示例 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和与其连通的O保留，内部被包围的O变为X。

• 示例 2：

输入: board = [["X"]]
输出: [["X"]]

💻 解题思路

思路：DFS 标记边界连通区域，再翻转内部 O

算法步骤

1. 获取网格尺寸 m, n。
2. 初始化 visited 二维数组，标记已访问的格子。
3. 定义 DFS 函数 dfs(x, y)：
   • 如果坐标越界、已访问或当前格子不是 'O'，则返回。
   • 将当前坐标存入 boards 列表（表示该格子与边界连通，不应翻转）。
   • 标记 visited[x][y] = True。
   • 对上下左右四个方向递归调用 dfs。
4. 从边界上的所有格子出发，调用 dfs：
   • 遍历第一列和最后一列：dfs(i, 0) 和 dfs(i, n-1)。
   • 遍历第一行和最后一行：dfs(0, j) 和 dfs(m-1, j)。
5. 遍历整个矩阵，如果 board[i][j] == 'O' 且 (i, j) 不在 boards 列表中，则该格子是内部被包围的 'O'，将其改为 'X'。
6. 原地修改完成，无需返回值。

代码实现

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        boards = []  # 存储与边界连通的 O 的坐标
        
        def dfs(x, y):
            if not (0 <= x < m and 0 <= y < n and not visited[x][y] and board[x][y] == "O"):
                return
            boards.append((x, y))
            visited[x][y] = True
            for dx, dy in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                dfs(dx, dy)
        
        # 从边界出发标记所有连通 O
        for i in range(m):
            dfs(i, 0)
            dfs(i, n-1)
        for j in range(n):
            dfs(0, j)
            dfs(m-1, j)
        
        # 翻转内部 O
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O" and (i, j) not in boards:
                    board[i][j] = "X"

📊 性能分析

• 时间复杂度：$O(m \times n)$，每个格子最多被访问一次。
• 空间复杂度：$O(m \times n)$，visited 数组和递归栈深度（最坏情况）。

思考

• 判断 (i, j) not in boards 效率较低（列表查找 $O(k)$），可使用布尔数组或直接标记原矩阵：例如将边界连通 O 临时改为其他字符（如 '#'），最后再统一恢复或翻转。更常见且高效的做法如下：

  # 标记边界连通 O 为 'A'
  # ...
  # 最后遍历：如果是 'A' 恢复为 'O'，如果是 'O' 改为 'X'

• 本题也可以使用 BFS（队列）避免递归深度过大。

思路二：DFS + 临时字符标记

算法步骤

1. 获取网格尺寸 m, n。
2. 定义 DFS 函数 dfs(x, y)：
   • 如果坐标越界或当前格子不是 'O'，则返回。
   • 将当前格子临时修改为 'A'（表示与边界连通的 'O'）。
   • 对四个方向递归调用 dfs。
3. 从边界出发：
   • 遍历第一列和最后一列：dfs(i, 0) 和 dfs(i, n-1)。
   • 遍历第一行和最后一行：dfs(0, j) 和 dfs(m-1, j)。
4. 遍历整个矩阵：
   • 如果 board[i][j] == 'O'，说明是内部被包围的 'O'，改为 'X'。
   • 如果 board[i][j] == 'A'，说明是与边界连通的 'O'，恢复为 'O'。
5. 原地修改完成，无需返回值。

代码实现

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
        
        def dfs(x, y):
            if not (0 <= x < m and 0 <= y < n and board[x][y] == "O"):
                return
            board[x][y] = "A"
            for dx, dy in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                dfs(dx, dy)
        
        # 标记边界连通 O 为 A
        for i in range(m):
            dfs(i, 0)
            dfs(i, n-1)
        for j in range(n):
            dfs(0, j)
            dfs(m-1, j)
        
        # 翻转内部 O 为 X，恢复边界连通 O 为 O
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                elif board[i][j] == "A":
                    board[i][j] = "O"

📊 性能分析

• 时间复杂度：$O(m \times n)$，每个格子最多被访问一次。
• 空间复杂度：$O(m \times n)$，递归栈深度最坏为连通区域大小（边界 O 可能布满整个网格）。

思考

• 本解法不需要额外的 visited 数组，因为标记为 'A' 后原本的 'O' 被覆盖，递归不会再重复访问同一格子。
• 这是本题最经典的解法之一，简洁且高效。
• 也可以使用 BFS（队列）替代 DFS，避免递归深度过大导致栈溢出（Python 默认递归深度约 1000），若网格很大推荐用 BFS。