lc1034-边界着色

题目描述

• 有一个二维地图，值代表颜色。
• 给定一个点的坐标和一个备用的颜色
• 这个点周围与它颜色一样的部分认为是一个整体
• 给这块区域的最外层刷上备用颜色

示例

输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
输出：[[3,3],[3,2]]

输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
输出：[[1,3,3],[2,3,3]]

输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
输出：[[2,2,2],[2,1,2],[2,2,2]]

题解

• 思路：模拟、flood fill
  1. 使用 flood fill 找到这个颜色块
  2. 找的时候顺便标记边界
  3. 给边界上色

var (n, m inttarget intdx, dy = [4]int{-1, 0, 1, 0}, [4]int{0, 1, 0, -1}
)func colorBorder(grid [][]int, row int, col int, color int) [][]int {n, m = len(grid), len(grid[0])target = grid[row][col]st := make([][]int, n) // 0: default, 1: block, 2: borderfor i := 0; i < n; i ++ { st[i] = make([]int, m) }dfs(row, col, grid, st)for i := 0; i < n; i ++ {for j := 0; j < m; j ++ {if st[i][j] == 2 {grid[i][j] = color}}}return grid
}func dfs(x, y int, grid, st [][]int) {is_border := falsefor d := 0; d < 4; d ++ {r, c := x + dx[d], y + dy[d]if 0 <= r && r < n && 0 <= c && c < m && grid[r][c] == target {if st[r][c] == 0 {st[r][c] = 1dfs(r, c, grid, st)}} else {is_border = true}}if is_border { st[x][y] = 2 }
}