【floodfill深搜】图像渲染，这题不来试试？
【floodfill深搜】图像渲染，这题不来试试？
文章目录
- 733. 图像渲染
- 解题思路：floodfill 算法（暴力搜索）
733. 图像渲染
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[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，因为它不是在上下左右四个方向上与初始点相连的像素点。示例 2:
输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]提示:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], newColor < 2160 <= sr < m0 <= sc < n
解题思路：floodfill 算法（暴力搜索）
首先我们先得知道 floodfill 算法是解决什么问题的，其实就是可以把一个二维数组中多个数值看作是高度，那么就会有平原、山地、盆地的区分，那些小的并且接壤的数字就相当于是盆地，稍微高一点的就是平原或者山地了，而 floodfill 算法就是要求出在高处放水之后，这些盆地的水位就高了多少！
比如说这道题的例一，上半部分的 1 和下半部分的 1 被中间的 0 所隔开了，相当于 0 就是一个峡谷或者悬崖类似的地形，但是这道题比较简单，就是要求与 [sr, sc] 位置接壤的地块，将它们的数值改成新的数值，这其实就跟我们前面所学的深度优先遍历、回溯都是类似的，只不过在细节处理上有所不同罢了！
而对于 floodfill 算法，用 深度优先遍历和广度优先遍历 都是可以处理的，我们这里就以深度优先遍历为例展开叙述！
相信通过前面的刷题量，这道题写起来是比较轻松的，无非就是在递归函数中稍微修改细节即可！比如这道题要求与 [sr, sc] 位置接壤并且数值相同的地块才进行修改，那么我们==只需要从 [sr, sc] 位置处出发，深度优先遍历其旁边满足要求的路径进行修改数值==即可！
并且同样这道题也是 需要使用 used 数组来标记当前元素是否已经走过，防止重复递归后栈溢出！又因为我们回溯之后其实不需要对当前元素去掉已经走过的标记，所以是不需要回溯操作的！
如果我们采用的是前序遍历修改当前元素的数值的话，那么在递归之前就得先记录下 [sr, sc] 处的数值，防止前序遍历修改之后，后面的递归层拿到的是修改后的数值，就不匹配了！
class Solution {
private:
bool used[50][50]; // 标记该元素是否已经走过
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int oldcolor = image[sr][sc]; // 先记录下[sr, sc]处原来的数值
dfs(image, oldcolor, color, sr, sc);
return image;
}
void dfs(vector<vector<int>>& image, int oldcolor, int newcolor, int x, int y)
{
// 递归函数出口
if(x < 0 || x == image.size() || y < 0 || y == image[x].size() || used[x][y] == true || image[x][y] != oldcolor)
return;
used[x][y] = true;
image[x][y] = newcolor; // 前序方式修改数值
// 后递归处理
dfs(image, oldcolor, newcolor, x + 1, y);
dfs(image, oldcolor, newcolor, x - 1, y);
dfs(image, oldcolor, newcolor, x, y + 1);
dfs(image, oldcolor, newcolor, x, y - 1);
}
}; 当然，我们也可以使用后序方式修改数值，此时因为数值是最后回溯的时候才修改的，所以不需要关心递归下去的递归层会拿不到原来 [sr, sc] 的数值，所以我们只需要改变一下修改数值的先后顺序即可！
class Solution {
private:
bool used[50][50]; // 标记该元素是否已经走过
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
dfs(image, sr, sc, color, sr, sc);
return image;
}
void dfs(vector<vector<int>>& image, int sr, int sc, int color, int x, int y)
{
// 递归函数出口
if(x < 0 || x == image.size() || y < 0 || y == image[x].size() || used[x][y] == true || image[x][y] != image[sr][sc])
return;
// 先递归处理
used[x][y] = true;
dfs(image, sr, sc, color, x + 1, y);
dfs(image, sr, sc, color, x - 1, y);
dfs(image, sr, sc, color, x, y + 1);
dfs(image, sr, sc, color, x, y - 1);
image[x][y] = color; // 后序方式修改数值
}
};腾讯云开发者
