搜索
查看
编辑修改
首页
UNITY
NODEJS
PYTHON
AI
GIT
PHP
GO
CEF3
JAVA
HTML
CSS
搜索
码创造者
这个屌丝很懒,什么也没留下!
关注作者
热门标签
jquery
HTML
CSS
PHP
ASP
PYTHON
GO
AI
C
C++
C#
PHOTOSHOP
UNITY
iOS
android
vue
xml
爬虫
SEO
LINUX
WINDOWS
JAVA
MFC
CEF3
CAD
NODEJS
GIT
Pyppeteer
article
热门文章
1
自动化办公:openpyxl操作Excel的7个示例_openpyxl应用实例
2
算法沉淀——动态规划之回文串问题(上)(leetcode真题剖析)_回文串相关算法题
3
<Rust><GUI>rust语言GUI库tauri体验:前、后端结合创建一个窗口并修改其样式
4
用 ONLYOFFICE 宏帮你自动执行任务:介绍与教程_onlyoffice宏
5
Spring源码编译常见问题解决方案_gradle-7.5.1-bin
6
U盘或者移动硬盘弹出时出现弹窗的解决方法_移动硬盘怎么解除占用并安全弹出
7
初次使用 uni.chooseLocation 方法时可能会出现延迟或无效果的情况
8
Mac M1 Pycharm的安装及使用_pycharm mac m1
9
LittleVGL_lvgl 设计器
10
Java小抄(二)|Java中字符串占位符替换的多种实现方法_java 字符串占位符替换
当前位置:
article
> 正文
递归、搜索与回溯算法:FloodFill 算法_搜索floodfill
作者:码创造者 | 2024-07-19 08:01:10
赞
踩
搜索floodfill
例题一
算法思路:
可以利⽤「深搜」或者「宽搜」,遍历到与该点相连的所有「像素相同的点」,然后将其修改成指定的像素即可。
全局变量:
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/码创造者/article/detail/850292
推荐阅读
article
【
资料
、
指导
】
23
电赛
无人机
G题满分国一,比赛
指导
、
方案
、
代码
、
电路板
等
资料
_
23
年
电赛
无人机
...
本文介绍了20
23
年全国大学生电子设计大赛中,空地协同智能消防系统的
无人机
和小车项目,涉及激光雷达定位
、
SLAM算法
、
精...
赞
踩
article
GitLab
+
Jenkins
+
Maven
+
Docker
实现
自动
集成、打包、
部署
_能实现从gitlib...
目录⭐
自动
集成流程:流程图:环境准备Java环境安装Git工具安装
Maven
工具安装
GitLab
代码管理仓库安装Jenk...
赞
踩
article
Docker+
Jenkins
+
Maven
+
Gitee
持续集成详细配置_
docker
安装jenkin...
这里直接开始配置
jenkins
,如果还不太清楚怎么安装
jenkins
可以访问之前的文章:记录在
docker
中安装Jenk...
赞
踩
article
px4
源码中
的
疑问和记录
_
px4
moduleparams
(
nullptr
)
代码
解析
...
1、在类BlockLocalPositionEstimator定义了很多私有成员如下 // general parame...
赞
踩
article
解决
py
to
rch
报错 RuntimeError: An attempt
has
been ma...
报错信息运行
py
to
rch
代码报错,BrokenPipeError: [Errno 32] Broken
pipe
,...
赞
踩
article
如果你还没玩过
Docker
Stack
管理
服务
,你已经out了,(送
Portainer
集群
管理
教程)...
我们上面使用swarm部署
服务
,单个
服务
还好,如果很多个
服务
怎么来解决呢,这里就用到了
Docker
Stack
管理
服务
。...
赞
踩
article
前端
使用
webSocket
与
后台
建立
连接
并进行心跳监测机制...
2.在页面初始化的时候调用getWebSocket此方法。首先项目中需要引入websocket。
前端
使用
webSocke...
赞
踩
article
使用
idea
把一个
git
分支
的部分
提交
记录
合并
到另一个
git
分支
上_
idea
合并
部分
提交
...
本文详细描述了如何在IntelliJIDEA中使用Git的Cherry-Pick功能,将用户在future-vvip-i...
赞
踩
article
C语言
——
递归函数
之计算
阶乘
...
递归函数
是一种在函数体内调用自身以解决问题的特殊函数。它通过不断将问题分解为更小的相同类型的问题,直到达到一个可以直接解...
赞
踩
article
JAVA
网络
编程中
TCP
和UDP_
java
网络
编程
tcp
udp
...
网络
的相关概念
网络
通信概念:两台设备之间通过
网络
实现数据传输
网络
通信:将数据通过
网络
从一台设备传输到另一台设备
java
....
赞
踩
article
使用
ChatGPT4
协助完成
读取
文件
中不同字的数量_
chatgpt4
文章识别...
使用
ChatGPT4
协助完成
读取
文件
中不同字的数量_
chatgpt4
文章识别
chatgpt4
文章识别 ...
赞
踩
article
Hadoop
-30
ZooKeeper
集群
Java
API 客户端 POM
Java
操作ZK
监听
节...
上一节完成了ZK的命令操作:创建、读取、删除
节点
等操作。本节用
Java
API进行操作,实现创建、删除、
监听
节点
、
监听
变化...
赞
踩
article
从攻击视角看
代码
隐私
安全
,9款
Git
秘密
扫描
工具盘点_
gitleaks
...
代码
隐私信息泄露的危害性不容忽视。无论是错误放置的密钥,或是意外泄露的数据库密码都可能会转化为即时危机,带来沉重的经济损...
赞
踩
article
redis
常用命令
、
数据类型
、
redis
.
conf
配置文件
、备份策略讲解_
redis
命令行
...
Redis命令(https://www.
redis
.net.cn/order/)
redis
是一种nosql(not on...
赞
踩
article
vs2017
+
openni
2
+
opencv343
人脸活体检测_
openni
人脸检测...
if (faces.size() > 0) { for (int i = 0; i < faces...
赞
踩
article
python
-
django
运行时提示ModuleNotFoundError: No
module
n...
python
-
django
运行时提示ModuleNotFoundError: No
module
named
'requ...
赞
踩
article
知识图谱
和
LLM
:利用
Neo4j
驾驭大型
语言
模型(探索真实
用例
)...
它们能够适应不同的对话环境、回答各种主题的问题,甚至模拟创意写作,彻底改变了人类与机器的互动方式,引发了新一波人工智能应...
赞
踩
article
【计算机
文献
案例】关于
java
的外语
文献
_
java
英文
参考
文献
_
java
web外文
参考
文献
近三年
...
下面是搜素整理的
java
英文
参考
文献
的分享,供大家借鉴参考。特别是写毕业设计文章的时候,将会用到。_
java
web外文参...
赞
踩
article
Redis
配置文件
_
redis
-
server
指定
配置文件
...
redis
配置属性详解_
redis
-
server
指定
配置文件
redis
-
server
指定
配置文件
...
赞
踩
article
IM
即时通讯
项目
框架分析_
im
项目
...
推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Red...
赞
踩
相关标签
无人机
硬件工程
stm32
自动化集成
GitLab
Jenkins
Docker
Maven
jenkins
docker
ci
px4
lpe导航
pytorch
深度学习
python
java
程序员
前端
websocket
网络协议
intellij-idea
git
c语言
开发语言