热门标签
热门文章
- 1离线存储网页服务器无响应,网页保存应注意的问题
- 2大数据分析培训课程python时间序列预测SARIMAX模型教程
- 3【算法】动态规划法_如何从动态规划算法所生成的表中
- 4在安卓手机上安装Ubuntu详细教程(无需root)_安卓无root装ubuntu
- 5最新互联网大厂职位薪资，快来对号入座吧_大厂架构师年薪结构
- 6Do not mutate vuex store state outside mutation handlers.
- 7pmp公式整理一览_pmp 静态回收期 动态回收期
- 8load a PyTorch model from a TF 2.0 checkpoint, please set from_tf=True
- 9＜el-tabs＞Tabs 标签页增加标签页按钮样式优化_el-tabs before-leave
- 10Macbook M1版安装安卓模拟器_mac m1 安卓模拟器
当前位置: article > 正文
递归、搜索与回溯算法：FloodFill 算法
作者：繁依Fanyi0 | 2024-05-03 00:32:26
赞
踩
递归、搜索与回溯算法：FloodFill 算法
例题一
算法思路：
可以利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。
全局变量：
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
int m, n;
int precolor;//记录原先的颜色
int m, n;
int precolor;//记录原先的颜色
递归函数设计：void dfs(vector<vector<int>>& image,int i,int j,int color)
•
参数：
a.
原始矩阵；
b.
当前所在的位置；
c.
需要修改成的颜⾊。
•
函数体：
a.
先将该位置的颜⾊改成指定颜⾊（因为我们的判断，保证每次进⼊递归的位置都是需要修改的
位置）；
b.
遍历四个⽅向上的位置：
▪
如果当前位置合法，并且与初试颜⾊相同，就递归进去。
例题二
算法思路：
遍历整个矩阵，每次找到「⼀块陆地」的时候：
•
说明找到「⼀个岛屿」，记录到最终结果 ret
⾥⾯；
•
并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「标记」。这样的话，我们下次遍历到这块岛屿的时候，就不会再记录了，不会影响最终结果。
•
其中「标记」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是
733. 图像渲染
这道题~
这样，当我们，遍历完全部的矩阵的时候，
ret
存的就是最终结果。
全局变量：
int ret;
int m, n;
vector<vector<bool>> visited;
int dx[4] = { 0,0,1,-1 }, dy[4] = {1,-1,0,0};
int m, n;
vector<vector<bool>> visited;
int dx[4] = { 0,0,1,-1 }, dy[4] = {1,-1,0,0};
解法（dfs）：void dfs(vector<vector<char>>& grid,int i,int j）
算法流程：
1.
初始化 ret = 0
，记录⽬前找到的岛屿数量;
2.
双重循环遍历⼆维⽹格，每当遇到⼀块陆地，标记这是⼀个新的岛屿，然后将这块陆地相连的陆地全部变成海洋。
递归函数的设计：
1.
把当前格⼦标记为true；
2.
向上、下、左、右四格递归寻找陆地，只有在下标位置合理的情况下，才会进⼊递归：
a.
下⼀个位置的坐标合理；
b.
并且下⼀个位置是陆地
例题三
算法思路：
•
遍历整个矩阵，每当遇到⼀块⼟地的时候，就⽤「深搜」或者「宽搜」将与这块⼟地相连的「整个岛屿」的⾯积计算出来。
•
然后在搜索得到的「所有的岛屿⾯积」求⼀个「最⼤值」即可。
•
在搜索过程中，为了「防⽌搜到重复的⼟地」：
◦
可以开⼀个同等规模的「布尔数组」，标记⼀下这个位置是否已经被访问过；
◦
也可以将原始矩阵的 1
修改成
0
，但是这样操作会修改原始矩阵。
4.
解法（深搜 dfs）：
算法流程：
•
主函数内：
a.
遍历整个数组，发现⼀块没有遍历到的⼟地之后，就⽤ dfs
，将与这块⼟地相连的岛屿的⾯积求出来；
b.
然后将⾯积更新到最终结果 ret
中。
•
深搜函数 dfs
中：
a.
能够进到 dfs
函数中，说明是⼀个没遍历到的位置；
b.
标记⼀下已经遍历过，设置path = 1
（当前这个位置的⾯积为
1
），记录最终的⾯积；
c.
上下左右遍历四个位置：
▪
如果找到⼀块没有遍历到的⼟地，就将与这块⼟地相连的岛屿⾯积累加到 path
上；
d.
循环结束后， path
中存的就是整块岛屿的⾯积，返回即可。
全局变量：
vector<vector<bool>> visited;
int m, n;
int path;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
int m, n;
int path;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
函数：void dfs(vector<vector<int>>& grid, int i, int j)
例题四
解法：
算法思路：
正难则反。
可以先利⽤
dfs
将与边缘相连的
'0'
区域做上标记，然后重新遍历矩阵，将没有标记过的
'0'
修改成
'X'
即可。
例题五
解法：
算法思路：
正难则反。
如果直接去判断某⼀个位置是否既能到⼤西洋也能到太平洋，会重复遍历很多路径。
我们反着来，从⼤西洋沿岸开始反向
dfs
，这样就能找出那些点可以流向⼤西洋；同理，从太平洋沿岸也反向 dfs
，这样就能找出那些点可以流向太平洋。那么，被标记两次的点，就是我们要找的结果。
例题六
解法：
算法思路：
模拟类型的
dfs
题⽬。
⾸先要搞懂题⽬要求，也就是游戏规则。
从题⽬所给的点击位置开始，根据游戏规则，来⼀次
dfs
即可。
例题七
算法思路：
这是⼀道⾮常典型的「搜索」类问题。
我们可以通过「深搜」或者「宽搜」，从
[0, 0]
点出发，按照题⽬的「规则」⼀直往
[m - 1, n - 1] 位置⾛。 同时，设置⼀个全局变量。每次⾛到⼀个合法位置，就将全局变量加⼀。当我们把所有能⾛到的路都⾛完之后，全局变量⾥⾯存的就是最终答案。
4.
解法（dfs）：
算法流程：
•
递归函数设计：
a.
参数：当前所在的位置 [i, j]
，⾏⾛的边界
[m, n]
，坐标数位之和的边界
k
；
b.
递归出⼝：
i.
[i, j]
的坐标不合法，也就是已经超出能⾛的范围；
ii.
[i, j]
位置已经⾛过了（因此我们需要创建⼀个全局变量 visited
，来标记当前位置是否⾛过）；
iii.
[i, j]
坐标的数位之和⼤于
k
；
上述情况的任何⼀种都是递归出⼝。
c.
函数体内部：
i.
如果这个坐标是合法的，就将全局变量 ret++
；
ii.
然后标记⼀下 [i, j]
位置已经遍历过；
iii.
然后去 [i, j]
位置的上下左右四个⽅向去看看。
•
辅助函数：
a.
检测坐标 [i, j]
是否合法；
b.
计算出 i
，
j
的数位之和，然后与
k
作⽐较即可。
•
主函数：
a.
调⽤递归函数，从
[0 ,0]
点出发。
•
辅助的全局变量：
a.
⼆维数组 visited
：标记
[i, j]
位置是否已经遍历过；
b.
变量 ret
：记录⼀共到达多少个合法的位置。
c.
上下左右的四个坐标变换。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/526862
推荐阅读
相关标签
