题目#733.图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 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]内。

分析题意

经过分析，可以将上述题目总结为：从上下左右四个方向遍历图，找到与原始值相同的值，并将值修改为目标值，然后返回原数组，这题显然是一个深度有效搜索的题目。而我们首先需要做的就是构造一个递归方法，确定递归方法的入参。

确定入参

• 图 image
  既然要遍历整个图，那图一定少不了。但是我哪知道这个图上的某个点已经被遍历了呢？
• 标记图 map
  我们可以创建一个与image大小相同的标记图map，在每次遍历的时候，使用map标记已经遍历过的地点，能够避免重复遍历，也相当于剪枝操作，不然我们的代码将进入死循环，直接会爆栈内存溢出。
• 当前遍历的点x, y
  用x, y记录当前遍历的位置
• 原始值和新的值oldColor
  渲染需要将原始值替换成新的值
  在确定函数的入参之后，与往常一样，我们需要找到的还是以下两点：

确定函数结束条件与递归体

• 递归结束条件
  • 避免outOfIndex
    x !in 0..image.lastIndex || y !in 0..image[0].lastIndex
  • 去除已经遍历过的点
    map[x][y] == true
  • 去除不满足条件的点，即颜色不为原始值（只有原始值要替换成新的值）
    image[x][y] != oldColor

所以递归结束条件可以用以下代码展示：

if (x !in 0..image.lastIndex || y !in 0..image[0].lastIndex || map[x][y] || image[x][y] != oldColor) {
    return
}

• 递归体
  本题的递归体分为两个部分：

  • 状态修改
    遍历到的点修改颜色，并标记为已经遍历
    image[x][y] = newColor
map[x][y] = true
  • 四个方向递归
    dfs(image, map, x - 1, y, oldColor, newColor)
dfs(image, map, x, y - 1, oldColor, newColor)
dfs(image, map, x + 1, y, oldColor, newColor)
dfs(image, map, x, y + 1, oldColor, newColor)

  所以递归体的代码可写为：

  image[x][y] = newColor
  map[x][y] = true
  dfs(image, map, x - 1, y, oldColor, newColor)
  dfs(image, map, x, y - 1, oldColor, newColor)
  dfs(image, map, x + 1, y, oldColor, newColor)
  dfs(image, map, x, y + 1, oldColor, newColor)
  

最终代码

class Solution {
    fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, newColor: Int): Array<IntArray> {
        if (image.isEmpty() || image[0].isEmpty()) return image
        val map = Array(image.size) { BooleanArray(image[0].size) }
        dfs(image, map, sr, sc, image[sr][sc], newColor)
        return image
    }

    private fun dfs(image: Array<IntArray>, map: Array<BooleanArray>, x: Int, y: Int, oldColor: Int, newColor: Int) {
        if (x !in 0..image.lastIndex || y !in 0..image[0].lastIndex || map[x][y] || image[x][y] != oldColor) {
            return
        }
        image[x][y] = newColor
        map[x][y] = true
        dfs(image, map, x - 1, y, oldColor, newColor)
        dfs(image, map, x, y - 1, oldColor, newColor)
        dfs(image, map, x + 1, y, oldColor, newColor)
        dfs(image, map, x, y + 1, oldColor, newColor)
    }
}