733.画面渲染(javascript)733.FloodFill

有一幅以 m x n 二维整数数组表示图片。 image ，其中 image[i][j] 指示图片的像素值大小。

你也有三个整数 sr , sc 和 newColor 。应该从像素开始。 image[sr][sc] 从图像开始 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标。 上下、左右方向 与初始坐标具有相同像素值的连接像素，然后记录与它们对应的这四个方向的合格像素。 四个方向 具有与初始坐标相同像素值的连接像素，……，重复此过程。更改所有记录像素的颜色值 newColor 。

最后返回 颜色渲染后的图像 。

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

示例 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，因为它不是在上下、左右方向与初始点相连的像素点。

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

示例 2:

输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]

提示:

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], newColor < 216
• 0 <= sr < m
• 0 <= sc < n

js宽度首次遍历(BFS)深度优先遍历(DFS）

1，深度优先算法

遍历规则：沿顶点的深度方向连续遍历。顶点的深度方向是指其相邻方向。

深度优先搜索算法(Depth-First-Search):是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，搜索尽可能深的树的分支。当节点v搜索的边缘已被探索，或者节点在搜索过程中不符合条件。搜索将返回到发现节点。v该边的起始节点。重复整个过程，直到访问所有节点。

深度优先遍历和宽度优先遍历

深度优先是自上而下的遍历搜索。 首先是逐层遍历。

两者之间的区别
对于算法 这无非是时间换空间。 时间的空间ui

深度优先级不需要记住所有节点, 因此，占用的空间很小。, 广度首先需要记录所有节点，占用大量空间。
深度优先有回溯练习(没有路可走，你需要回头。)所以时间相对较长。
深度首先采用堆栈的形式。, 也就是说，在高级
宽度首先采用队列的形式, 即先进先出

宽度优先算法

var floodFill = function (image, sr, sc, newColor) {
    let m = image.length
    let n = image[0].length
    let oldColor = image[sr][sc]//指定[sr][sc]位置上的颜色是旧颜色。
    if (oldColor == newColor) {//当发现指定位置的颜色与替换颜色相同时，无需替换并返回原始数组。
        return image
    }
    var queue = [[sr, sc]]//初始化新数组以保存需要更改的位置。
   //queue 当数组中没有值时跳出循环
    while (queue.length) {
        //queue.shift()，获取列表中的第一项，然后在数组中删除该项以更改颜色。
        let [i, j] = queue.shift()
        image[i][j] = newColor
        //以i，j为中心--上下左右，同时不超过限值image[sr][sc]（指定位置上的颜色）相同，请将位置保存在中。queue数组里面
        if (i - 1 >= 0 && image[i - 1][j] == oldColor) queue.push([i - 1, j])
        if (j - 1 >= 0 && image[i][j - 1] == oldColor) queue.push([i, j - 1])
        if (i + 1 < m && image[i + 1][j] == oldColor) queue.push([i + 1, j])
        if (j + 1 < n && image[i][j + 1] == oldColor) queue.push([i, j + 1])
    }
    return image
};

深度优先算法

//主要步骤：
//1构建递归函数，函数参数应至少包括主题需求所使用的参数。
//2。找到边界，递归函数首先列出递归结束的条件，即满足要求或超出范围。
//3。然后列出可能移动或更改的所有路径。
var dfs= function (step,...) {
    if()  // 判断边界（不符合条件、跳过、不操作）
      {   
         return 
       }
    // 枚举每个可能的(满足条件)
    //执行的操作
   dfs(step+1,...);
   dfs(step-2,...);

var floodFill = function (image, sr, sc, newColor) {
    let m = image.length
    let n = image[0].length
    let oldColor = image[sr][sc]//指定[sr][sc]位置上的颜色是旧颜色。
    if (oldColor == newColor) {//当发现指定位置的颜色与替换颜色相同时，无需替换并返回原始数组。
        return image
    }
    var fill = function (i, j) {
    //以i，j居中，超出边界，和image[sr][sc]（指定位置的颜色）不同且不工作
        if (i < 0 || i >= m || j < 0 || j >= n || image[i][j] != oldColor) {
            return
        }
        //符合条件-更换颜色
        image[i][j] = newColor
        //数字上下、左右递归。
        fill(i - 1, j)
        fill(i, j - 1)
        fill(i + 1, j)
        fill(i, j + 1)
    }
    fill(sr, sc)
    return image
};

leetcode： https://leetcode.cn/problems/flood-fill/