欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 社会 > 专题五:floodfill算法(太平洋大西洋水流问题)

专题五:floodfill算法(太平洋大西洋水流问题)

2025/5/21 3:18:37 来源:https://blog.csdn.net/Laydya/article/details/148069043  浏览:    关键词:专题五:floodfill算法(太平洋大西洋水流问题)

以leetcode417题为例

题目解析: 

 

整张图,左边深蓝的是太平洋,右边浅蓝的是大西洋,你需要在矩阵中找到一个点,使其可以流向太平洋又可以流向大西洋,并且你每次流的时候只能由高到低,或者相等到相等

算法原理解析: 

第一种解法:暴力枚举每一个点是否能流向太平洋和大西洋,也就是一行一行的枚举每一个点

                     但可能会有重复的路径的枚举,而且会不断的dfs,可能会超时

第二种解法:正难则反,看太平洋的水能由哪留到,也就是枚举从低到高的点,就是水能蔓延的哪

比如从太平洋每一个最上一行和最左一列的每一个点可以蔓延到哪,所有绿色框起来的都可以

在枚举最下面一行和右边一列的所有点能蔓延到哪,

 

所有重复的点就是可以到太平洋和大西洋 (红色三角可以流向大西洋和绿色方块流向太平洋) 

代码编写:

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词