题目:
编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image 表示,元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
请用新颜色填充初始坐标点的周围区域,并返回填充后的图像。
示例:
输入:
image =[[1,1,1],[1,1,0],[1,0,1]]sr = 1,sc = 1,newColor = 2
输出:
[[2,2,2],[2,2,],[2,0,1]]
解释:
初始坐标点位于图像的正中间,坐标 (sr,sc)=(1,1)。
初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2。
注意,右下角的像素没有更改为 2,因为它不属于初始坐标点的周围区域。
解题思路:
1.首先要保存初始颜色值,以便后续判断是否是连续的
2.定义四个方向的偏移量,上下左右
3.分别找四个方向的坐标,将符合条件的进行颜色更新
源代码如下:文章来源地址https://www.toymoban.com/news/detail-664748.html
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};//分别是上下左右四个方向
const int dy[4] = {0, 1, -1, 0};
void dfs(vector<vector<int>>& image, int x, int y, int color, int newColor) {
//如果当前坐标的颜色是初始颜色
if (image[x][y] == color) {
//更新当前坐标的颜色
image[x][y] = newColor;
//递归地找上下左右四个方向
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
//新坐标在图像的范围内,才进行递归,否则继续找其他方向的
if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size()) {
dfs(image, mx, my, color, newColor);
}
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
//记录初始颜色值
int currColor = image[sr][sc];
//需要更新的颜色不是初始颜色,开始递归
if (currColor != newColor) {
dfs(image, sr, sc, currColor, newColor);
}
//返回原数组
return image;
}
};
这道题还可以用广度优先遍历来实现,借助队列,在队列中通过pair对保存坐标的x,y。
将四个方向中符合条件的坐标入队,再进行更新颜色文章来源:https://www.toymoban.com/news/detail-664748.html
源代码如下:
class Solution {
public:
const int dx[4]={1,0,0,-1};
const int dy[4]={0,1,-1,0};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];//保存初始颜色值
//如果要更新的颜色值与初始值相同,就不用改了,直接返回数组
if (currColor == newColor) {
return image;
}
//记录图像的行和列
int n = image.size(), m = image[0].size();
//在队列中保存的是一个个pair对
queue<pair<int, int>> que;
//先将初始值入队
que.emplace(sr, sc);
//初始坐标更新颜色
image[sr][sc] = newColor;
while (!que.empty()) {
//取坐标
int x = que.front().first, y = que.front().second;
//坐标出队
que.pop();
//查找四个方向的坐标是否相连
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
//坐标需要在图像范围内且与初始坐标相连,也就是与初始颜色相同
if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
//坐标入队
que.emplace(mx, my);
//更新颜色
image[mx][my] = newColor;
}
}
}
return image;
}
};
到了这里,关于leetcode原题:颜色填充(经典的递归问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!