LeetCode 130. 被围绕的区域

题目描述
给定一个 m x n 的矩阵 board，由字符 'X' 和 'O' 组成。你需要找到所有被 'X' 围绕的区域，并将这些区域中的所有 'O' 用 'X' 填充。
关键规则：

• 任何边界上的 'O' 都不会被填充为 'X'。
• 任何与边界上的 'O' 相连（上下左右四个方向）的 'O' 也不会被填充。
• 被围绕的区域是指不与边界相连且被 'X' 包围的所有 'O'。

示例
输入：

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' 即为需要填充的。
2. 核心步骤：
   • 从所有边界上的 'O' 开始，进行深度优先搜索（DFS）或广度优先搜索（BFS），标记所有相连的 'O' 为特殊符号（如 '#'），表示这些是保留的 'O'。
   • 遍历整个矩阵，将未被标记的 'O'（即被包围的）改为 'X'，同时将标记 '#' 恢复为 'O'。

详细步骤

步骤 1：标记边界相连的 'O'

• 遍历矩阵的四条边（第一行、最后一行、第一列、最后一列）。
• 如果遇到 'O'，启动 DFS/BFS，将所有相连的 'O' 标记为 '#'。

以 DFS 为例的标记过程：

def dfs(board, i, j):
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
        return
    board[i][j] = '#'  # 标记为保留
    dfs(board, i+1, j) # 下
    dfs(board, i-1, j) # 上
    dfs(board, i, j+1) # 右
    dfs(board, i, j-1) # 左

步骤 2：遍历边界并触发标记

for i in range(len(board)):
    for j in range(len(board[0])):
        if (i == 0 or i == len(board)-1 or j == 0 or j == len(board[0])-1) and board[i][j] == 'O':
            dfs(board, i, j)  # 标记边界相连区域

步骤 3：转换矩阵

• 遍历整个矩阵：
  • 将 'O'（未被标记，说明被包围）改为 'X'。
  • 将 '#'（标记的保留区域）恢复为 'O'。

for i in range(len(board)):
    for j in range(len(board[0])):
        if board[i][j] == 'O':
            board[i][j] = 'X'
        elif board[i][j] == '#':
            board[i][j] = 'O'

完整代码示例（DFS 实现）

def solve(board):
    if not board:
        return
    
    m, n = len(board), len(board[0])
    
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
            return
        board[i][j] = '#'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    # 标记边界相连的 'O'
    for i in range(m):
        for j in range(n):
            if (i == 0 or i == m-1 or j == 0 or j == n-1) and board[i][j] == 'O':
                dfs(i, j)
    
    # 转换矩阵
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == '#':
                board[i][j] = 'O'

复杂度分析

• 时间复杂度：O(m × n)，每个节点最多被访问一次。
• 空间复杂度：O(m × n)，DFS 的递归栈在最坏情况下可能覆盖整个矩阵。

关键点总结

• 逆向思维：从边界出发标记保留区域，避免直接处理复杂的内部分割。
• DFS/BFS 用于连通性标记，确保所有与边界相连的 'O' 被正确识别。
• 最后通过统一遍历完成转换，保证逻辑清晰。