当前位置: article > 正文

递归、搜索与回溯算法：FloodFill 算法_floodfile算法、记忆化搜索

作者：Guff_9hys | 2024-08-19 17:19:44

踩

floodfile算法、记忆化搜索

例题一

算法思路：

可以利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。

全局变量：

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. 上下左右的四个坐标变换。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/1003171?site