颜色填充
编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image
表示,元素为初始颜色值。初始坐标点的行坐标为 sr
列坐标为 sc
。需要填充的新颜色为 newColor
。
「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
请用新颜色填充初始坐标点的周围区域,并返回填充后的图像。
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
//如果新值和旧值一样,就没必要涂了
if(newColor == image[sr][sc]){
return image;
}
dfs(image,sr,sc,newColor,image[sr][sc]);
return image;
}
public void dfs(int[][] image, int sr, int sc, int newColor, int oldColor){
if(sr < 0 || sr >= image.length || sc < 0||sc >= image[sr].length || image[sr][sc]!=oldColor)
return;
image[sr][sc] = newColor;
dfs(image,sr-1,sc,newColor,oldColor);
dfs(image,sr+1,sc,newColor,oldColor);
dfs(image,sr,sc-1,newColor,oldColor);
dfs(image,sr,sc+1,newColor,oldColor);
}
}‘
解法一:深度优先搜索
解法二:广度优先搜索
此方法是深度优先搜索(递归)