1034：边界着色（1578 分）

Ian

2019-04-28 约 590 字预计阅读 2 分钟次阅读

力扣第 134 场周赛第 2 题

题目

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

如果两个方块在任意 4 个方向上相邻，则称它们相邻。

如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。

连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：

在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
在网格的边界上（第一行/列或最后一行/列）

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

并返回最终的网格 grid 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j], color <= 1000
0 <= row < m
0 <= col < n

相似问题：

0463：岛屿的周长

分析

连通问题，依然可以用并查集，连通后，遍历 (row,col) 所在连通块的格子，判断是否边界即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        def find(x):
            if f[x] != x:
                f[x] = find(f[x])
            return f[x]

        def union(x, y):
            f[find(x)] = find(y)

        m, n = len(grid), len(grid[0])
        f = list(range(m*n))
        for i, j in product(range(m), range(n)):
            a = grid[i][j]
            if i and grid[i-1][j]==a:
                union(i*n+j,(i-1)*n+j)
            if j and grid[i][j-1]==a:
                union(i*n+j,i*n+j-1)
        res,fa = [],find(row*n+col)
        for i, j in product(range(m), range(n)):
            if find(i*n+j)==fa:
                for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                    if not (0<=x<m and 0<=y<n and find(x*n+y)==fa):
                        res.append((i,j))
                        break
        for i,j in res:
            grid[i][j] = color
        return grid

59 ms

目录

1034：边界着色（1578 分）

题目

分析

解答