Hex.*

LC1034 - Coloring a Border

Posted on In
Datastructure and Algorithm: DAY 50. Leetcode: 203/2710

Description

You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.
Two squares belong to the same connected component 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).
You should color the border of the connected component that contains the square grid[row][col] with color.
Return the final grid.

Example 1:
Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

Example 2:
Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]

Example 3:
Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
Output: [[2,2,2],[2,1,2],[2,2,2]]

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

Solutions

How to define connected component boundaries?

  1. The color is the same as grid[row][col] and connected to the connected component. These two conditions must be met
  2. When a point that satisfies the above conditions appears in the outermost circle, it must be a boundary.
  3. When a point that meets the above conditions appears in the inner circle, if there is a point around it with a different color than grid[row][col], it is the boundary.

So…

  • we should find out all the connected components and set the value to -1
  • then we should found all the boundaries and add them to a set.
  • convert components equal to -1 to color if they are in boundaries, otherwise, convert them back to the original color.
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
from collections import deque
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])
        queue = deque([(row, col)])
        ori = grid[row][col]
        grid[row][col] = -1
        while queue:
            r, c = queue.popleft()
            for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
                nx, ny = r+dx, c+dy
                if 0<=nx<m and 0<=ny<n and grid[nx][ny] == ori:
                    grid[nx][ny] = -1
                    queue.append((nx,ny))
        
        # find boarders
        edge = set()
        for r in range(m):
            for c in range(n):
                for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
                    nx, ny = r+dx, c+dy
                    if nx < 0 or nx >= m or ny <0 or ny >= n or grid[nx][ny] != -1:
                        edge.add((r, c))
                        break
        
        # color the item in edge and revert the other -1 back to original color
        for r in range(m):
            for c in range(n):
                if grid[r][c] == -1:
                    if (r,c) in edge:
                        grid[r][c] = color
                    else:
                        grid[r][c] = ori
        return grid