题目大意：
图像渲染
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 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， 因为它不是在上下左右四个方向上与初始点相连的像素点。
注意:
- image 和 image[0] 的长度在范围 [1, 50] 内。
- 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
- image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=733
解题思路分析：
解法一：BFS
看完题目描述，仿佛复习了一遍bfs广度优先搜索的概念。本题中图像渲染从起始点开始向四周扩散，凡是相邻的元素与起始点元素相同，它将被渲染成新的颜色，同时再向四周扩散。如果当前位置与其实点的颜色不同，则不再向外扩散。这是一个典型的bfs思路。如果你对bfs并不熟悉，可以参考我之前总结的入门文章：LEETCODE常见算法之广度优先搜索BFS超详细白话讲解
实现代码：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int color=image[sr][sc]; // 起始点颜色
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; // 扩散的四个方向
// 记录已访问过的节点，避免重复访问
boolean[][] visited = new boolean[image.length][image[0].length];
visited[sr][sc]=true; // 起始节点设置为已访问
Queue<int[]> q = new LinkedList<>(); // queue中记录当前被扩散到的点
q.offer(new int[]{sr,sc}); // 将起始节点加入Queue
while(q.size()>0){ // 遍历Queue中元素
int[] node = q.poll(); // 取出Queue中一个元素
if(image[node[0]][node[1]]==color){ // 当前元素等于其实元素
image[node[0]][node[1]]=newColor; // 将当前元素设置为新颜色
for(int[] dir : dirs){ // 当前元素向四个方向扩散
// 扩散后的当前点
int r=dir[0]+node[0],c=dir[1]+node[1];
// 如果该点在矩阵范围内，并且它没被访问过
if(r>=0&&r<image.length&&c>=0
&&c<image[0].length&&!visited[r][c]){
// 将该点的访问状态设为true
visited[r][c]=true;
// 将该点加入queue
q.offer(new int[]{r,c});
}
}
}
}
return image;
}本题解法执行时间为2ms。
Runtime: 2 ms, faster than 17.93% of Java online submissions for Flood Fill.
Memory Usage: 40.3 MB, less than 89.47% of Java online submissions for Flood Fill.
解法二：DFS
实际上很多BFS的题目都能够转为使用DFS深度优先搜索来解题，同理，DFS也能转化为BFS。对于本题，两者在时间复杂度上并没有太大的差别，不过DFS不需要使用到Queue，因此在执行时间上略微优于BFS。
DFS时，我们依旧以起点坐标作为DFS的起点。对于当前点，如果它的颜色等于起始点，那么我们将当前点设置为新的颜色。同时，DFS向下递归到它相邻的四个点，处理逻辑与上层递归完全相同。与bfs相似，我们也需要使用到一个访问数组来记录已经访问过的所有点，避免重复访问。
关于深度优先搜索：LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)
实现代码：
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int color=image[sr][sc];
boolean[][] visited = new boolean[image.length][image[0].length];
visited[sr][sc]=true;
dfs(image,sr,sc,newColor,color,visited);
return image;
}
void dfs(int[][] image,int sr,int sc,int newColor,int oldColor,boolean[][] visited){
image[sr][sc]=newColor;
for(int[] dir : dirs){
int r=dir[0]+sr,c=dir[1]+sc;
if(r>=0&&r<image.length&&c>=0&&c<image[0].length
&&!visited[r][c]&&image[r][c]==oldColor){
visited[r][c]=true;
dfs(image,r,c,newColor,oldColor,visited);
}
}
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 52.41% of Java online submissions for Flood Fill.
Memory Usage: 40.9 MB, less than 81.58% of Java online submissions for Flood Fill.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-733-flood-fill-解题思路分析/