Algorithm


Problem Name: 1034. Coloring A Border

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

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const colorBorder = function(grid, r0, c0, color) {
  const dirs = [[-1,0], [1,0], [0,1], [0,-1]]
  const c = grid[r0][c0]
  const rows = grid.length
  const cols = grid[0].length
  const visited = Array.from({length: rows}, () => new Array(cols).fill(0))
  dfs(r0, c0, c, rows, cols, visited, grid, dirs)
  for(let i = 0; i  <  rows; i++) {
    for(let j = 0; j  <  cols; j++) {
      if(visited[i][j] === -1) {
         if(i === 0 || j === 0 || i === rows - 1 || j === cols - 1) {
            visited[i][j] = -2
         } else {
            for(let dir of dirs) {
              if(visited[i + dir[0]][j + dir[1]] === 0) {
                 visited[i][j] = -2
                 break
              }
            }    
         }
      }
    }
  }
  for(let i = 0; i < rows; i++) {
    for(let j = 0; j  <  cols; j++) {
      if(visited[i][j] === -2) grid[i][j] = color
    }
  }
  
  return grid
};

function dfs(row, col, target, rows, cols, visited, grid, dirs> {
  if(row >= rows || col >= cols || row < 0 || col < 0 || grid[row][col] !== target || visited[row][col] === -1) {
    return   
  }
  visited[row][col] = -1
  for(let dir of dirs) {
    dfs(row + dir[0], col+dir[1], target, rows, cols, visited, grid, dirs>
  }
  
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
grid = [[1,1],[1,2]], row = 0, col = 0, color = 3

Output

x
+
cmd
[[3,3],[3,2]]

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        def dfs(i, j):
            seen.add((i, j))
            if not (0 < i < m - 1 and 0 < j < n - 1 and grid[i - 1][j] == grid[i + 1][j] == grid[i][j - 1] == grid[i][j + 1] == grid[i][j]):
                matrix[i][j] = 0
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                if 0 <= x < m and 0 <= y < n and grid[x][y] == self.tar and (x, y) not in seen:
                    dfs(x, y)
        m, n = len(grid), len(grid[0])
        seen = set()
        self.tar = grid[r0][c0]
        matrix = [row[:] for row in grid]
        dfs(r0, c0)
        for i in range(m):
            for j in range(n):
                if not matrix[i][j]:
                    matrix[i][j] = color
        return matrix
Copy The Code & Try With Live Editor

Input

x
+
cmd
grid = [[1,1],[1,2]], row = 0, col = 0, color = 3

Output

x
+
cmd
[[3,3],[3,2]]
Advertisements

Demonstration


Previous
#1033 Leetcode Moving Stones Until Consecutive Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1035 Leetcode Uncrossed Lines Solution in C, C++, Java, JavaScript, Python, C# Leetcode