773.图像渲染 | Cluas's blog

原题

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值 （行，列） 和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:

image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 **[0, 65535]**内。

解题思路

看到题目第一反应就是对指定点的四个方向做递归搜索，搜索遇到边界后返回结果。而搜索既可以采用bfs，又可以采用dfs。

dfs

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
    var (
        dx = []int{1, 0, 0, -1}
        dy = []int{0, 1, -1, 0}
    ) 
    var dfs func(image [][]int, x, y, color, newColor int) 
    dfs = func(image [][]int, x, y, color, newColor int) {
        if image[x][y] == color {
            image[x][y] = newColor
            for i := 0; i < 4; i++ {
                mx, my := x + dx[i], y + dy[i]
                if mx >= 0 && mx < len(image) && my >= 0 && my < len(image[0]) {
                    dfs(image, mx, my, color, newColor)
                }
            }
        }
    }  
    currColor := image[sr][sc]
    if currColor != newColor {
        dfs(image, sr, sc, currColor, newColor)
    }
    return image
}

bfs

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
     var (
        dx = []int{1, 0, 0, -1}
        dy = []int{0, 1, -1, 0}
    ) 
    currColor := image[sr][sc]
    if currColor == newColor {
        return image
    }
    n, m := len(image), len(image[0])
    queue := [][]int{}
    queue = append(queue, []int{sr, sc})
    image[sr][sc] = newColor
    for i := 0; i < len(queue); i++ {
        cell := queue[i]
        for j := 0; j < 4; j++ {
            mx, my := cell[0] + dx[j], cell[1] + dy[j]
            if mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor {
                queue = append(queue, []int{mx, my})
                image[mx][my] = newColor
            }
        }
    }
    return image
}

总结

遇到这种带方向的，好多都可以套模版。

// 先定义四个方向的变化量，再依次遍历方向
var (
    dx = []int{1, 0, 0, -1}
    dy = []int{0, 1, -1, 0}
) 
// 到达边界，do someting...
if 到达边界 {
    do something...
}