Leetcode 1034 Coloring A Border

发表于 |

给定一个二维矩阵grid，矩阵中的值代表在矩阵那处位置的颜色。
相连的颜色被认为是一个连通区域。

连通区域的边界是指那些和不属于该连通区域的块相连的部分，或者是处于整个矩阵的边界处的部分。

给定一个位置(r0, c0)，和一个颜色color。将(r0, c0)所在连通区域的颜色全部改成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, grid.length[0] <= 50
  2. 1 <= grid[i][j] <= 100
  3. 0 <= r0 <= grid.length
  4. 0 <= c0 <= grid[0].length
  5. 1 <= color <= 1000

思路分析：
这道题就是单纯的dfs，然后判断连通区域的点是不是在边界上。

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
29
30
31
32
33
34
35
class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        n,m = len(grid), len(grid[0])
        tmp = grid[r0][c0]
        # dfs找连通区域所有点
        vis = set()
        def dfs(grid, i, j):
            for x,y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                if 0<=x<n and 0<=y<m and (x,y) not in vis and grid[x][y] == tmp:
                    vis.add((x,y))
                    dfs(grid, x, y)
        
        vis.add((r0,c0))
        dfs(grid, r0, c0)
        
        # check()找边界点
        def check(i,j):
            if i in (0,n-1) or j in (0,m-1): return True
            for x,y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                if grid[x][y] != tmp: return True
            return False
        
        res = []
        for x,y in vis:
            if check(x,y): res.append((x,y))
        # 修改边界点
        for x,y in res:
            grid[x][y] = color
        
        return grid

# 154 / 154 test cases passed.
# Status: Accepted
# Runtime: 96 ms, beats 96.15%
# Memory Usage: 13.2 MB