Surrounded Regions,LeetCode,130

题目描述（LeetCode 130: Surrounded Regions）：

给定一个二维字符数组 board，包含 'X' 和 'O'，捕获所有被 'X' 围绕的区域，并将这些区域中的 'O' 全部变为 'X'。

一个区域被围绕是指该区域中所有 'O' 都与 board 的边界不相邻。

示例：

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

运行你的函数后，board 应该被修改为：

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

解题思路：

1. 深度优先搜索（DFS）：
   • 从 board 的边界开始，找到所有与边界相连的 'O'，将这些 'O' 标记为 '-'（或其他非 'X' 和 'O' 的字符）。
   • 遍历整个 board，将所有未被标记为 '-' 的 'O' 变为 'X'，将所有 '-' 变回 'O'。
2. 广度优先搜索（BFS）：
   • 类似于 DFS，但从边界上的 'O' 开始，使用队列进行广度优先搜索，标记所有与边界相连的 'O'。
   • 最后同样遍历 board 进行替换。
3. 并查集（Union-Find）：
   • 使用并查集将所有边界上的 'O' 与一个虚拟节点连接。
   • 遍历 board，将所有 'O' 进行合并。
   • 最后检查每个 'O' 是否与虚拟节点相连，不相连的变为 'X'。

详细代码实现（DFS 方法）：

class Solution: def solve(self, board: List[List[str]]) -> None: if not board or not board[0]: return

    rows, cols = len(board), len(board[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = '-'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # 遍历边界上的 'O' 并进行 DFS
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)

    # 替换字符
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == '-':
                board[r][c] = 'O'
            else:
                board[r][c] = 'X'

解释：

1. 边界检查：
   • 首先检查 board 是否为空或没有元素。
2. DFS 函数：
   • dfs 函数用于深度优先搜索，将边界上的 'O' 及其相连的 'O' 标记为 '-'。
3. 遍历边界：
   • 遍历 board 的四条边界，对每个边界上的 'O' 调用 dfs 函数。
4. 替换字符：
   • 最后遍历整个 board，将所有 '-' 变回 'O'，其余的 'O' 变为 'X'。

复杂度分析：

• 时间复杂度：O(rows * cols)，需要遍历整个 board。
• 空间复杂度：O(rows * cols)，最坏情况下递归栈的深度。

这种方法有效地利用了深度优先搜索的特性，从边界出发，逐步标记所有不被 'X' 围绕的 'O'，最终完成题目要求。