专栏首页HUC思梦的java专栏和同事谈谈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题也是类似的思路,小伙伴们可以自己去试试怎么解决,欢迎留言一起讨论。

之后的文章,我也会不定期的分享一些有关算法刷题的解题方案,和小伙伴们一起研究解题套路,毕竟有些公司还是会考一些算法的嘛。

好了本文就到这里,欢迎大家持续关注!

往期文章推荐:

中间件专辑:

什么是消息中间件?主要作用是什么?

常见的消息中间件有哪些?你们是怎么进行技术选型的?

你懂RocketMQ 的架构原理吗?

聊一聊RocketMQ的注册中心NameServer

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 详解股票买卖算法的最优解(二)

    本文作为补充文章,对更复杂的题目进行解答,如果还没有阅读上篇文章,希望小伙伴们先去看一下上篇文章:详解股票买卖算法的最优解(一),有助于理解。

    HUC思梦
  • 详解股票买卖算法的最优解(一)

    主要用的技巧是“状态机”,那么什么是“状态机”呢?没听过的小伙伴会觉得它很高大尚,但今天我们讨论过后,你会发现其实它就是那么回事。

    HUC思梦
  • EL中定义函数

    HUC思梦
  • Java中如何通过一个类名来调用另一个类的静态方法?

    所以,比如另一个类叫OtherClass,它的静态公有方法是 public static int MethodA() {...}

    黑泽君
  • 我的第6个京东618

    今年是我的第6个618,因为入职的时间比较"合适",使得我经历了每年两次完整的大促备战。那年还在北辰,618的当晚,我记忆的很清晰,接近凌晨1点左右的时候,我们...

    王新栋
  • 进程管理利器-supervisor部署记录

    一、简单介绍 supervisor是用来管理进程的一个工具,止于为什么要用supervisor,是因为相对于linux传统的进程管理方式来说,它有很多的优势: ...

    洗尽了浮华
  • 归并排序

    归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。分治法就是将一个大问题分解成小问题然后递归求解,然后再将小问题的结果合并...

    Haley_Wong
  • 高翔Slambook第七讲代码解读(3d-3d位姿估计)

    上回咱们读完了pose_estimation_3d2d.cpp这个程序,也找到了3d-2d位姿估计与2d-2d位姿估计之间的联系与差别:

    小白学视觉
  • 直方图均衡化及matlab实现

    chenjx85
  • 如何解决Transaction 注解,方法内部调用无效问题

    Transaction 注解开启事务,是通过代理对象对方法进行封装开启和关闭事务,但生效的的条件是外部调用,而内部调用并不会走代理对象,这就造成了事务失效。

    海涛

扫码关注云+社区

领取腾讯云代金券