[130][中等][并查集][DFS] 被围绕的区域

题目描述

130. 被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

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' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解题思路

DFS

矩阵中有X和O两种字母, 但其实有三种元素:

• 字母 X

• 被字母 X 包围的字母 O

• 没有被字母 X 包围的字母 O

任何边界上的 O 都不会被填充为 X, 所有的不被包围的 O 都直接或间接与边界上的 O 相连, 我们可以利用这个性质判断 O 是否在边界上.

我们遍历所有边界位置, 从每一个的O开始, 搜索与之相连的O, 这些O最终都不会被置为X. 而剩余的O最终会被置为X. 因此在搜索过程中, 将边界上的O, 以及所有与之相连的O, 都临时置为#. 最后再统一的, 将矩阵中剩余的O置为X, 再将#恢复成O.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if n == 0:
            return board
        m = len(board[0])

        def dfs(i, j):
            if not 0 <= i < n or not 0 <= j < m:
                return
            if board[i][j] != 'O':
                return

            board[i][j] = '#'
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        for i in range(n):
            dfs(i, 0)
            dfs(i, m - 1)
        for j in range(m):
            dfs(0, j)
            dfs(n - 1, j)

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

并查集

并查集的思路也比较直观. 对于矩阵中的O, 我们将相连的O相连接, 组成一个集合. 而且, 我们知道不会被填充的O肯定是边界处的O或与之相连, 因此, 我们在为所有的O初始化集合编号时, 将所有边界上的O的祖先定义为同一个特殊的值.

棋盘是二维的, 每个位置的祖先编号仍然是一个数值, 因此我们需要将每个二维坐标映射到一维的唯一数字, 常用的方法就是位置递增编号, 对于二维坐标(x, y), 映射为x * m + y, 其中m是二维矩阵的列数. 这样共得到0, 1, ..., m * n - 1这些编号索引. 再加上上面说的边界上的O的共同祖先, 我们将其定义为m * n, 这种就得到了共m * n + 1个编号.

使用普通的并查集方法对齐进行查找合并, 最终遍历所有O的位置, 判断其最先是否为m * n, 对于不是的填充为X.

class Union:
    def __init__(self, n):
        self.roots = list(range(n))

    def find(self, i):
        if self.roots[i] == i:
            return i
        self.roots[i] = self.find(self.roots[i])
        return self.roots[i]

    def union(self, a, b):
        self.roots[self.find(a)] = self.find(b)

    def connected(self, a, b):
        return self.find(a) == self.find(b)


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if n == 0:
            return board
        m = len(board[0])
        dummy = m * n

        u = Union(m * n + 1)

        for i in range(n):
            if board[i][0] == 'O':
                u.union(i * m, dummy)
            if board[i][m - 1] == 'O':
                u.union(i * m + m - 1, dummy)
        for j in range(m):
            if board[0][j] == 'O':
                u.union(j, dummy)
            if board[n - 1][j] == 'O':
                u.union((n - 1) * m + j, dummy)

        directs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O':
                    for row, col in directs:
                        if 0 <= i + row < n and 0 <= j + col < m and board[i + row][j + col] == 'O':
                            u.union((i + row) * m + j + col, i * m + j)

        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O' and not u.connected(i * m + j, dummy):
                    board[i][j] = 'X'