【LeetCode】733.图像渲染（深度优先搜索，java实现）
题目
链接
分析
这道题非常简单，其实就是让你遍历当前图形的所有节点，并且修改颜色为新颜色就好了。通过dfs和bfs都能实现。代码如下：
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if(image[sr][sc]==newColor) return image;
coloring(image,sr,sc,image[sr][sc],newColor);
return image;
}
public void coloring(int[][] image,int x,int y,int oldColor,int newColor){
if(x<0 || x>=image.length || y<0 || y>=image[0].length || image[x][y]!=oldColor){
return ; //坐标越界和不同色的情况
}
image[x][y] = newColor; //上色
coloring(image,x+1,y,oldColor,newColor);
coloring(image,x-1,y,oldColor,newColor);
coloring(image,x,y+1,oldColor,newColor);
coloring(image,x,y-1,oldColor,newColor);
}
}
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if(newColor==image[sr][sc]) return image;
int h=image.length, w=image[0].length; //记录image的长宽
int[][] direct = {{0,1},{0,-1},{1,0},{-1,0}}; //移动方向的数组
Queue<int[]> q = new LinkedList<>(); //队列
q.offer(new int[]{sr,sc}); //队列保存的是位置坐标
int oldColor = image[sr][sc]; //记录旧颜色
while(!(q.size()==0)){
int[] p = q.poll(); //取出队首元素
image[p[0]][p[1]] = newColor; //上色
for(int[] d: direct){ //将四周相同颜色的点的位置入队
int new_sr = p[0]+d[0];
int new_sc = p[1]+d[1];
if(new_sr>=0 && new_sr<h && new_sc>=0 && new_sc<w && image[new_sr][new_sc]==oldColor){
q.offer(new int[]{new_sr,new_sc});
}
}
}
return image;
}
}