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

题目大意 #

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量

边界：在连通分量的块中（前提）并且满足以下条件之一： （1）要么上下左右存在一个块不在连通分量里面 （2）要么这个块的位置在整个grid的边框上

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的连通分量的边界进行着色，并返回最终的网格 grid 。

解题思路 #

• 用 bfs 进行遍历选出边界，使用 color 给边界着色

代码 #

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})
	}
}