递归、搜索与回溯算法:FloodFill 算法

发布于:2024-04-25 ⋅ 阅读:(32) ⋅ 点赞:(0)

例题一

算法思路:
可以利⽤「深搜」或者「宽搜」,遍历到与该点相连的所有「像素相同的点」,然后将其修改成指定的像素即可。
全局变量:
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
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};
解法(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 };
函数: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. 上下左右的四个坐标变换。

网站公告

今日签到

点亮在社区的每一天
去签到