[leetcode] 1034. Coloring A Border

[leetcode] 1034. Coloring A Border

Description

Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.

Example 1:

Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3Output: [[3, 3], [3, 2]]

Example 2:

Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3Output: [[1, 3, 3], [2, 3, 3]]

Example 3:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]

Note:

1 <= grid.length <= 501 <= grid[0].length <= 501 <= grid[i][j] <= 10000 <= r0 < grid.length0 <= c0 < grid[0].length1 <= color <= 1000

分析

题目的意思是：给你一个数组，给定位置（r0,c0）的连通分量，并将边界赋为给定color。解决方法为判断给定位置四个边界，（注意是将边界涂色，所以非边界要保持原来的颜色）并递归向外进行扩展判断，如果四个边不全，则进行上色。

如下面就是把grid[1][3]的位置的边界图上颜色1，其中grid[1][1]位置为非边界，所以不用上颜色1，其他的则需要上颜色1.

[[1,2,1,2,1,2],[2,2,2,2,1,2],[1,2,2,2,1,2]]131

[[1,1,1,1,1,2],[1,2,1,1,1,2],[1,1,1,1,1,2]]

递归遍历的时候记录边界点（border），和遍历过的点(seen)，防止重复遍历。

代码

class Solution: def dfs(self,grid,i,j,cur,seen): if(i<0 or i>=len(grid) or j<0 or j>=len(grid[0])): return if((i,j) in seen): return seen.add((i,j)) if(grid[i][j]==cur): if(i==0 or i==len(grid)-1 or j==0 or j==len(grid[0])-1): self.border.add((i,j)) elif(grid[i-1][j] != cur or grid[i][j-1] != cur or grid[i+1][j] != cur or grid[i][j+1] != cur): self.border.add((i,j)) self.dfs(grid,i-1,j,cur,seen) self.dfs(grid,i+1,j,cur,seen) self.dfs(grid,i,j-1,cur,seen) self.dfs(grid,i,j+1,cur,seen) def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]: seen=set() cur=grid[r0][c0] self.border=set() self.dfs(grid,r0,c0,cur,seen) for item in self.border: grid[item[0]][item[1]]=color return grid

参考文献

​​Python DFS faster than 100% Easy to understand​​​​LeetCode-1034 Coloring A Border​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。