有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在
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，
因为它不是在上下左右四个方向上与初始点相连的像素点。
解法一：BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<int>xs = {1,0,-1,0};
vector<int>ys = {0,1,0,-1};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int num = image[sr][sc],width = image.size(),height = image[0].size();
if(image[sr][sc] == newColor){
return image;
}
queue<pair<int,int>> que;
que.emplace(sr,sc);
image[sr][sc]=newColor;
while(!que.empty()){
int x = que.front().first;
int y = que.front().second;
que.pop();
for(int i = 0;i<4;i++){
int mx = x+xs[i];
int my = y-ys[i];
if(mx>=0 && mx<width && my>=0 && my<height && image[mx][my]==num){
que.emplace(mx,my);
image[mx][my] = newColor;
}
}
}
return image;
}
};
|
使用队列表示已染色的元素。先入队并染色第一个元素，然后只要队列不空就循环：出队一个，判断上下左右四个元素是否合法，合法的话就入队并染色。
知识点：
- queue
- 添加元素到队尾是emplace()或者push，区别是emplace是新建一个对象并添加，push是添加一个已有对象。
- 删除队头元素：pop()，注意它没返回值
- 获取队头元素：front()
- pair
- pair表示一对元素，定义：
pair(type1,type2) name
- 获取或更改内容使用
pair.first pair.second
解法二：DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<int>xs = {1,0,-1,0};
vector<int>xy = {0,1,0,-1};
void dfs(vector<vector<int>>& image,int sr,int sc,int collor,int newColor){
if(image[sr][sc] == collor){
image[sr][sc] = newColor;
for(int i = 0;i<4;i++){
int x = sr + xs[i];
int y = sc + xy[i];
if(x >= 0&& x < image.size() && y >= 0 && y < image[0].size()){
dfs(image,x,y,collor,newColor);
}
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
if(image[sr][sc] != newColor){
dfs(image,sr,sc,image[sr][sc],newColor);
}
return image;
}
};
|
写起来较容易，深度优先需要先定义一个dfs递归函数。如果当前可以染色就染色，并且对上下左右中合法的元素使用dfs，主函数直接调用即可。