【BFS/DFS 解决 FloodFill 算法】图像渲染

题目链接：733. 图像渲染

题目解析

首先介绍一下什么是FloodFill算法：

FloodFill算法，也称为洪水填充算法，指的是在区域中找到性质相同的联通块，注意这里的联通块指的是上下左右相邻，斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。

我们回到题目，题目给我们一个由整数组成的二维矩阵image，其中的数字表示像素值。题目同时给出sr、sc和color分别表示起始位置 image[sr][sc] 和 目标色块。

我们需要从起始位置开始，找到所有与初始位置色块相邻的其他色块（色块相同）并将色块修改成color。

例一：

• image = [ [ 1, 1, 1 ], [ 1, 1, 0 ], [ 1, 0, 1 ] ]
• sr = 1, sc = 1, color = 2

image 表示为如下网格：

所有红色的区域就是性质相同的联通块。

修改后的 image 网格：

例二：

• image = [ [ 0, 0, 0 ], [ 0, 0, 0 ] ]
• sr = 0, sc = 0, color = 0

这个例子中其实位置的像素值与 color 一致，无需修改直接返回即可。

方向向量

在继续之前，有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右四个方向的操作。

坐标〖i, j〗的上下左右四个坐标是在i和j加上了 0、1、-1 ：

• 上下坐标：〖i + (-1), j + 0〗和〖i + 1, j + 0〗；
• 左右坐标：〖i + 0, j + (-1)〗和〖i + 0, j + 1〗。

因此需要定义两个向量坐标：dx = {0, 0, -1, 1}，dy = {-1, 1, 0, 0}。

在需要访问时，通过 〖row, col〗坐标和四次循环依次访问即可。

BFS：广度优先遍历

算法原理

1. 我们使用一个队列存储需要被修改像素值的方格的坐标（以数组的形式表示坐标）
2. 然后当队列不为空时就一直弹出队首元素，将该位置的像素值修改
3. 修改完成后，循环四次访问该位置的四周：通过队首元素得到的坐标，计算该位置的上下左右四个方向的坐标并检查合法性，将合法的位置存入队列中准备修改
4. 当层序遍历完成后，返回修改后的图像即可

细节问题

边界情况

从示例 2 可以知道，可能存在原像素值与color相同的情况。

这种情况下我们不需要修改任何方格，直接返回原图像即可。

代码实现

classSolution{// 辅助访问某位置上下左右四个方向的方向向量int[]dx={0,0,-1,1};int[]dy={-1,1,0,0};publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intoriginColor=image[sr][sc];// 记录原色像素值if(originColor==color){// 处理边界情况returnimage;}intm=image.length,n=image[0].length;// 记录图像的尺寸Queue<int[]>queue=newArrayDeque<>();// 用队列记录需要修改的色块的坐标queue.offer(newint[]{sr,sc});// 从位置[sr,sc]开始宽搜// 层序遍历while(!queue.isEmpty()){int[]top=queue.poll();// 获取队首introw=top[0],col=top[1];// 记录坐标image[row][col]=color;// 修改色块// 从位置[row,col]的上下左右四个方向宽搜for(intk=0;k<4;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==originColor){// 符合需要被修改的条件，入队queue.offer(newint[]{x,y});}}}// 返回修改后的结果returnimage;}}

DFS：深度优先遍历

算法原理

1. 直接从起始位置开始深搜
2. 对每一个指定位置的上下左右四个方向按照特定的条件搜索，然后修改其像素值为 color，直到没有符合条件的方格为止
3. 当所有方格被搜索过之后，递归结束，返回修改后的图像即可

全局变量

为了递归方便，我们将题目给出的image改为全局变量，同时m和n记录矩阵的大小。

然后是originColor用于记录起始位置的原像素值，题目给出的color，然后是两个向量数组dx和dy。

int[][]image;intoriginColor,color,m,n;int[]dx={0,0,-1,1};int[]dy={-1,1,0,0};

dfs 函数

函数头

dfs 函数的任务是帮助我们搜索指定位置的上下左右四个方位并且根据指定条件修改方格的像素值。

我们这里的参数是某个位置的坐标row和col，函数的返回值为 void。

dfs(introw,intcol);

函数体

我们循环四次，然后判断坐标是否合法，如果合法就看看：

1. 该位置的像素值是否与起始位置的原像素值相同
2. 该位置的像素值是否与 color 不同

如果同时满足 “与起始位置的原像素值相同” 和 “与 color 不同”，就将该位置的像素值修改成 color，然后基于这个位置继续深搜。

细节问题

边界情况

当原像素值与color相同，不需要修改，直接返回原图像即可。

代码实现

classSolution{int[][]image;intoriginColor,color,m,n;int[]dx={0,0,-1,1};int[]dy={-1,1,0,0};publicint[][]floodFill(int[][]givenImage,intsr,intsc,intgivenColor){image=givenImage;color=givenColor;m=image.length;n=image[0].length;// 从[sr,sc]位置开始递归，递归前先记录原像素值originColor=image[sr][sc];// 判断当前的像素值是否与color相同，不同就修改if(originColor!=color){image[sr][sc]=color;}dfs(sr,sc);returnimage;}privatevoiddfs(introw,intcol){// 从[row,col]位置开始向四个方向搜索for(intk=0;k<4;k++){intx=row+dx[k],y=col+dy[k];// 判断下标是否合法if(x>=0&&x<m&&y>=0&&y<n){// 判断当前位置的像素值是否与起始位置的像素值相同，并且是否与color不同if(image[x][y]==originColor&&image[x][y]!=color){// 修改像素值image[x][y]=color;dfs(x,y);}}}}}

文章到这里就告一段落了，若有错误请尽管指出～

完