边界着色

题目链接

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一 连通分量 。

连通分量的边界 是指连通分量中的所有与不在分量中的网格块相邻（四个方向上）的所有网格块，或者在网格的边界上（第一行/列或最后一行/列）的所有网格块。

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。

示例:

输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
输出：[[3,3],[3,2]]

思路

解法一：

用递归来实现深度优先搜索遍历连通分量，用一个大小和 grid 相同的矩阵 visited来记录当前节点是否被访问过，并把边界点存入数组borders 中。

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        border = []
        origin_color = grid[row][col]
        visited[row][col] = True
        self.dfs(grid, row, col, visited, border, origin_color)
        for x, y in border:
            grid[x][y] = color
        return grid

    def dfs(self, grid, x, y, visited, borders, origin_color):
        is_border = False
        m, n = len(grid), len(grid[0])
        direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == origin_color):
                is_border = True
            elif not visited[nx][ny]:
                visited[nx][ny] = True
                self.dfs(grid, nx, ny, visited, borders, origin_color)
        if is_border:
            borders.append((x, y))