1034. Coloring A Border #

Problem #

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

Problem Summary #

You are given an integer matrix grid of size m x n, representing a grid. You are also given three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.

When two grid squares have the same color and are adjacent in any of the four directions, they belong to the same connected component.

Border: a square in the connected component (as a prerequisite) that satisfies one of the following conditions: (1) There is a square above, below, left, or right that is not in the connected component (2) The square is located on the boundary of the entire grid

Use the specified color to color the border of the connected component containing the grid square grid[row][col], and return the final grid.

Solution Approach #

• Use bfs to traverse and select the border, then use color to color the border

Code #

package leetcode

type point struct {
	x int
	y int
}

type gridInfo struct {
	m             int
	n             int
	grid          [][]int
	originalColor int
}

func colorBorder(grid [][]int, row, col, color int) [][]int {
	m, n := len(grid), len(grid[0])
	dirs := []point{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	vis := make([][]bool, m)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	var borders []point
	gInfo := gridInfo{
		m:             m,
		n:             n,
		grid:          grid,
		originalColor: grid[row][col],
	}
	dfs(row, col, gInfo, dirs, vis, &borders)
	for _, p := range borders {
		grid[p.x][p.y] = color
	}
	return grid
}

func dfs(x, y int, gInfo gridInfo, dirs []point, vis [][]bool, borders *[]point) {
	vis[x][y] = true
	isBorder := false
	for _, dir := range dirs {
		nx, ny := x+dir.x, y+dir.y
		if !(0 <= nx && nx < gInfo.m && 0 <= ny && ny < gInfo.n && gInfo.grid[nx][ny] == gInfo.originalColor) {
			isBorder = true
		} else if !vis[nx][ny] {
			dfs(nx, ny, gInfo, dirs, vis, borders)
		}
	}
	if isBorder {
		*borders = append(*borders, point{x, y})
	}
}