1034-coloring-a-border.md

1034. Coloring A Border - 边框着色

给出一个二维整数网格 grid，网格中的每个值表示该位置处的网格块的颜色。

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

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

给出位于 (r0, c0) 的网格块和颜色 color，使用指定颜色 color 为所给网格块的连通分量的边界进行着色，并返回最终的网格 grid 。

 

示例 1：

输入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
输出：[[3, 3], [3, 2]]

示例 2：

输入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
输出：[[1, 3, 3], [2, 3, 3]]

示例 3：

输入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
输出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]

 

提示：

1. 1 <= grid.length <= 50
2. 1 <= grid[0].length <= 50
3. 1 <= grid[i][j] <= 1000
4. 0 <= r0 < grid.length
5. 0 <= c0 < grid[0].length
6. 1 <= color <= 1000

 

---

题目标签：Depth-first Search

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
python3	96 ms	13 MB

class Solution:
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    
    def dfs(self, g, m, v, i, j, c):
        # print(i, j)
        if i < 0 or i > len(g) or j < 0 or j > len(g[0]) or g[i][j] != c:
            return
        # 访问
        v[i][j] = 1
        # 判断是否符合涂色条件
        for di in range(4):
            x = i + __class__.dx[di]
            y = j + __class__.dy[di]
            if 0 <= x < len(g) and 0 <= y < len(g[0]) and g[x][y] == c:
                if not v[x][y]:
                    self.dfs(g, m, v, x, y, c)
            else:
                m[i][j] = 1
        
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        if not grid or not grid[0]:
            return grid
        if r0 < 0 or r0 > len(grid) or c0 < 0 or c0 > len(grid[0]):
            return grid
        c = grid[r0][c0]
        m = [ [0] * len(grid[0]) for _ in range(len(grid)) ]
        v = [ [0] * len(grid[0]) for _ in range(len(grid)) ]
        self.dfs(grid, m, v, r0, c0, c)
        for i in range(len(m)):
            for j in range(len(m[0])):
                if m[i][j]:
                    grid[i][j] = color
        return grid