130. 被围绕的区域

Difficulty
Medium
Tags
并查集
URL
https://leetcode-cn.com/problems/surrounded-regions/
Star
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
notion imagenotion image
输入：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' 相连的'O' 最终都会被填充为'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：
输入：board = [["X"]]
输出：[["X"]]
提示：
  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'
通过次数168,537提交次数370,873

法 1 并查集

本题使用的并查集有个技巧，就是将所有不需要修改的位置 专门归到一个特定的集合中！！
所以在做union的时候有个技巧，一定是把x 归到 集合 y
最后只需要判断 是否在这个特定的集合中。
题解
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])
        uf = UnionFind(m*n + 2) # 多出来两个状态用来维护是否需要填充
        for i in range(0, m):
            for j in range(0, n):
                if board[i][j] == "O":
                    for d in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
                        x, y = i + d[0], j + d[1]
                        if (m > x >= 0 and n >  y >= 0 and 
														board[x][y] == "O" and 
														uf.find(x*n+y) != n*m+1):  # 这里表示 已经归到该特定的集合中了，那就不要再归一次了
                            uf.union(x*n+y, i*n + j)
                    # 如果在边界，那就归到边界这一特定的集合中
                    if i == 0 or i == m-1 or j == 0 or j == n-1:
                  
                        uf.union(i*n+j, m*n+1)
                        
        
        for i in range(0, m):
            for j in range(0, n):
                if board[i][j] == "O" and uf.find(i*n+j) != m*n+1:
                    board[i][j] = "X"

   
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])

        return self.root[x]
		# 这里只能是 x 归到集合 y 
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)   
        self.root[root_x] = root_y

法 2 dfs

思路
从边界的 “O” 出发，将与之相邻的”O”先标记位”-”，然后第二次遍历board，将”-“修改回“O”,同时，将“O”修改位”X”
题解
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        visited = set()
        m, n = len(board), len(board[0])
        for i in range(0, len(board)):
            for j in range(0, len(board[0])):
                if board[i][j] == "O" and \
                    (i==0 or i==m-1 or j == 0 or j == n-1):
                    self.dfs(i, j, board, visited)
        # print(board)
        for i in range(0, len(board)):
            for j in range(0, len(board[0])):
                if board[i][j] == "-":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

    def dfs(self, raw, col, board, visited):
        if raw < 0 or raw >= len(board) or col < 0 or col >= len(board[0]):
            return

        if board[raw][col] == "X" or (raw, col) in visited:
            return
        visited.add((raw, col))
        board[raw][col] = "-" 
        
        for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            self.dfs(raw+d[0], col + d[1], board, visited)