和同事谈谈Flood Fill 算法
和同事谈谈Flood Fill 算法
前言
今天忙完了公司的工作后，发现同事在做LeeCode的算法题，顿时来了兴趣，于是王子与同事一起探讨如何能做好算法题，今天在此文章中和大家分享一下。
什么是Flood Fill 算法
我们今天谈论的是Flood Fill算法，那么什么是Flood Fill算法呢？
为了理解什么是Flood Fill算法，我们先抛开算法本身的概念，王子给大家说一些平时工作生活中的场景。
1.画图工具的填充功能
相信大家都用过Windows的画图工具，我们看下图
用颜料桶给一个图形区域染色，这就是比较典型的Flood Fill 算法的应用。
2.扫雷游戏
我们玩扫雷游戏的时候，当我们选中一块的时候，会向四周延展出一大片区域，那么有没有想过如果让你来实现这个算法，要怎么实现呢？这也是Flood Fill 算法的实际应用。
3.ps中的魔棒工具
在我们使用魔棒工具抠图的时候，原理其实也是一样的，选中一处后，将相连的相似颜色的部分选中，只不过这里面多了相似颜色的算法。
好了，看完以上的场景，相信小伙伴们对Flood Fill 算法应该有一个概念性的认识了，那么再做这种题之前，我们先考虑一下要做出这种题的套路，也可以说是一种框架思维。
Flood Fill 算法的解题框架
以上所有的例子都可以把它想成在一个图上进行操作，而图又可以叫做二维图形，既然是二维图形就可以给他加上坐标轴，（x,y）来代表一个像素点。
有了上边的想法后，继续思考，其实解决算法无外乎就是递归、遍历。
而这个问题就可以想象成一个4叉树的遍历问题，所以解题框架如下：
// (x, y) 为坐标位置
void fill(int x, int y) {
fill(x - 1, y); // 左
fill(x + 1, y); // 右
fill(x, y - 1); // 下
fill(x, y + 1); // 上
}这个框架其实很容易理解，对于四叉树结构，或者说二维矩阵的结构，这个框架基本都可以解决，从选中的像素点开始，向四周递归遍历，获得想要的结果。
有了框架的思维，那么我们就去找一道真题来看看吧。
真题解析
今天我们选择的真题是leecode上的733题，图像渲染，题目如下：
下面我们就根据框架思维写一下我们的解题步骤：
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
// 当前颜色
int origColor = image[sr][sc];
fill(image,sr,sc,origColor,newColor);
return image;
}
public void fill(int[][] image, int x, int y, int origColor, int newColor){
// 判断边界超出数组
if(!inArea(image,x,y)){
return;
}
// 判断边界遇到其他颜色
if(image[x][y]!=origColor){
return;
}
// 赋值新的颜色
image[x][y]=newColor;
// 引入框架
fill(image,x-1,y,origColor,newColor);
fill(image,x+1,y,origColor,newColor);
fill(image,x,y-1,origColor,newColor);
fill(image,x,y+1,origColor,newColor);
}
public Boolean inArea(int[][] image, int x, int y){
return x>=0&&x<image.length&&y>=0&&y<image[0].length;
}
}上边的注释写的已经跟完整了，希望小伙伴们动脑仔细看懂这段代码，看懂后你就明白了如何使用框架来解决问题了。
那么上边的就是正确答案吗，其实这段代码是有问题的，就是如果origColor和newColor如果相同的话，就会导致陷入无限递归。
那么如何解决呢？
最终答案
我们再次阅读上边的代码，可以知道出现无限递归的原因是每个坐标都要搜索上下左右，那么对于一个坐标，一定也会被上下左右的坐标多次重复搜索。所以我们必须保证重复搜索时能正确退出递归
其实针对于上边提到的这种情况，我们可以这样想，如果我们将元素的搜索路径记录下来，每次搜索时如果发现之前已经走过了这条路，那么就return，这样不就行了吗。
于是有了下边的最终答案
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
// 当前颜色
int origColor = image[sr][sc];
fill(image,sr,sc,origColor,newColor);
return image;
}
public void fill(int[][] image, int x, int y, int origColor, int newColor){
// 判断边界超出数组
if(!inArea(image,x,y)){
return;
}
// 判断边界遇到其他颜色
if(image[x][y]!=origColor){
return;
}
// 已经探索的origColor区域
if(image[x][y]==-1){
return;
}
// 赋值新的颜色之前先打一个标记，证明已经探索过
image[x][y]=-1;
// 引入框架
fill(image,x-1,y,origColor,newColor);
fill(image,x+1,y,origColor,newColor);
fill(image,x,y-1,origColor,newColor);
fill(image,x,y+1,origColor,newColor);
// 全部递归后，再把标记赋值成新的颜色
image[x][y]=newColor;
}
public Boolean inArea(int[][] image, int x, int y){
return x>=0&&x<image.length&&y>=0&&y<image[0].length;
}
}为什么要用-1做标记呢，其实这个无所谓，只要是一个题目中不会使用到的值就可以了（题目中规定值在0-65535之间）
说明一下，这种思路其实就是回溯算法
扩展算法
小伙伴们，上边的算法题如果已经弄明白了，那我们想一想，如果要实现PS的魔棒工具要怎么实现呢，我们来分析一下。
魔棒工具和上边的算法其实原理是一样的，只不过有两点不同，一是选择区域时选择的不是相同颜色，而是相似颜色，在ps中是可以根据阈值来设定相似程度的；二是使用魔棒选择区域后，在边界上会有边框，说明选中了哪些地方，这就变成了填充边界问题。
对于第一个问题很好解决，只要做如下改动即可
//原
// 判断边界遇到其他颜色
if(image[x][y]!=origColor){
return;
}
//新
// 遇到其他不在阈值内的颜色 threshold代表阈值
if (Math.abs(image[x][y] - origColor) > threshold){
return;
}
对于第二个问题，首先明确，我们要染色的部分只是边界，而不是内部区域，思考一下，内部区域的每个像素点的四周都是相同的颜色，而临近边界的像素点至少有一个方向的颜色与其不同，这就是解决问题的方案。这次我们使用visited数组来存储搜索路径，代码如下
class Solution {
boolean[][] visited = null;
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
// 当前颜色
int origColor = image[sr][sc];
// 初始化访问路径数组
visited = new boolean[image.length][image[0].length];
fill(image,sr,sc,origColor,newColor);
return image;
}
public int fill(int[][] image, int x, int y, int origColor, int newColor){
// 判断边界超出数组
if(!inArea(image,x,y)){
return 0;
}
// 判断边界遇到其他颜色
if(image[x][y]!=origColor){
return 0;
}
// 已经探索的origColor区域
if(visited[x][y]){
return 1;
}
// 赋值新的颜色之前先打一个标记，证明已经探索过
visited[x][y]=true;
// 引入框架
int result=
fill(image,x-1,y,origColor,newColor)+
fill(image,x+1,y,origColor,newColor)+
fill(image,x,y-1,origColor,newColor)+
fill(image,x,y+1,origColor,newColor);
// 全部递归后，如果result<4代表像素点是边界，赋值颜色
if(result<4){
image[x][y]=newColor;
}
return 1;
}
public Boolean inArea(int[][] image, int x, int y){
return x>=0&&x<image.length&&y>=0&&y<image[0].length;
}
}总结
以上详解了Flood Fill 算法解决的题目，其实掌握了这种框架思维，类似的题目都可以想出解决思路。
我们可以这么认为，做算法题就是要找到做题的套路，就像我们上学时做数学题，在其中不也是有些固定的套路吗。
leecode上边的1034题也是类似的思路，小伙伴们可以自己去试试怎么解决，欢迎留言一起讨论。
之后的文章，我也会不定期的分享一些有关算法刷题的解题方案，和小伙伴们一起研究解题套路，毕竟有些公司还是会考一些算法的嘛。
好了本文就到这里，欢迎大家持续关注！
往期文章推荐：
中间件专辑：