贵阳网站建设宏思锐达,普宁旅游网站设计方案,建设网站的法律可行性分析,php网站做多久题目#xff1a;
编写函数#xff0c;实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image 表示#xff0c;元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
「周围区域」是指颜色相同且在上、下、左…题目
编写函数实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 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.分别找四个方向的坐标将符合条件的进行颜色更新 源代码如下
class Solution {
public:const int dx[4] {1, 0, 0, -1};//分别是上下左右四个方向const int dy[4] {0, 1, -1, 0};void dfs(vectorvectorint 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);}}}}vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int newColor) {//记录初始颜色值int currColor image[sr][sc];//需要更新的颜色不是初始颜色开始递归if (currColor ! newColor) {dfs(image, sr, sc, currColor, newColor);}//返回原数组return image;}
};这道题还可以用广度优先遍历来实现借助队列在队列中通过pair对保存坐标的xy。
将四个方向中符合条件的坐标入队再进行更新颜色 源代码如下
class Solution {
public:const int dx[4]{1,0,0,-1};const int dy[4]{0,1,-1,0};vectorvectorint floodFill(vectorvectorint 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对queuepairint, 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;}
};
