当前位置: 首页 > news >正文

FloodFill算法——搜索算法

一、什么是FloodFill算法

FloodFill算法字面意思就是洪水灌溉法,比如我们有这么一块地:

        0表示平原,正数表示高地,负数表示凹地,那么当洪水来临时这些凹地会被优先灌满。而我们要找的正是这些联通块,如: 

 

        它是一种暴力搜索的思想,只要我们把每个地方都搜索一遍,那么最终的结果必定会水落石出。 通常可以使用BFS、DFS或并查集解决。

BFS(广度优先搜索)——搜索算法_广度优先搜索bfs-CSDN博客

DFS+回溯+剪枝(深度优先搜索)——搜索算法-CSDN博客

接下来我们直接从题中感受。

二、试题一:岛屿数量

        我们可以使用两层for循环找到没有搜索过的“1”然后在从这个“1”开始进行BFS或DFS展开,在期间使用哈希表记录每个“1”是否已经搜索过。每一次新的展开之前做一下计数,最后得到最终答案。

BFS代码示例:

class Solution {
public:int n=0,m=0,ret=0;int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};int numIslands(vector<vector<char>>& grid){n=grid.size(),m=grid[0].size(); vector<vector<bool>> hash(n,vector<bool>(m));for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(grid[i][j]=='1'&&!hash[i][j]) bfs(i,j,grid,hash);  return ret;}void bfs(int i,int j,vector<vector<char>>& grid,vector<vector<bool>>& hash){ret++;queue<pair<int,int>> q;hash[i][j]=true;q.push({i,j});while(!q.empty()){auto [a,b] = q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]=='1'&&!hash[x][y]){q.push({x,y});hash[x][y]=true;}}}}
};

 DFS代码示例:

class Solution {
public:int n=0,m=0,ret=0;int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};int numIslands(vector<vector<char>>& grid){n=grid.size(),m=grid[0].size();vector<vector<bool>> hash(n,vector<bool>(m));for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(grid[i][j]=='1'&&!hash[i][j]){ret++;dfs(i,j,grid,hash);}return ret;}void dfs(int i,int j,vector<vector<char>>& grid,vector<vector<bool>>& hash){hash[i][j]=true;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]=='1'&&!hash[x][y])dfs(x,y,grid,hash);}}
};

三、试题二:太平洋大西洋水流问题 

        按题意,如果一个数能够与上边界和左边界元素联通,那么它就能流入“太平洋”,如果与右边界或下边界元素联通则流入“大西洋” 。

        如果我们一个元素一个元素的去搜索,去看它流入“太平洋”,还是“大西洋”,那么效率势必会很低。我们可以直接从边界扩展,能被上边界和左边界扩展到的是“太平洋”,能被下边界和右边界扩展到的是“大西洋”。所以需要使用一个哈希表记录两个状态(“大西洋,“太平洋”),可以使用一个pair<bool,bool>作为哈希表的元素类型。

DFS代码示例: 

class Solution {
public:vector<vector<pair<bool,bool>>> hash;int n=0,m=0;vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights){n=heights.size(),m=heights[0].size();hash.resize(n);for(int i=0;i<n;i++) hash[i].resize(m,{false,false});for(int j=0;j<m;j++) dfs(0,j,heights,1),dfs(n-1,j,heights,2);for(int i=0;i<n;i++) dfs(i,0,heights,1),dfs(i,m-1,heights,2);vector<vector<int>> ret;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(hash[i][j].first&&hash[i][j].second) ret.push_back({i,j});return ret;}int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};void dfs(int i,int j,vector<vector<int>>& heights,int f){f==1?hash[i][j].first=true:hash[i][j].second=true;for(int k=0;k<4;k++){int x=dx[k]+i,y=dy[k]+j;if(x>=0&&x<n&&y>=0&&y<m&&heights[i][j]<=heights[x][y]){if(f==1&&hash[x][y].first) continue;if(f==2&&hash[x][y].second) continue;dfs(x,y,heights,f);}}}
};

BFS代码示例:

class Solution {
public:vector<vector<pair<bool,bool>>> hash;int n=0,m=0;vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights){n=heights.size(),m=heights[0].size();hash.resize(n);for(int i=0;i<n;i++) hash[i].resize(m,{false,false});for(int j=0;j<m;j++) bfs(0,j,heights,1),bfs(n-1,j,heights,2);for(int i=0;i<n;i++) bfs(i,0,heights,1),bfs(i,m-1,heights,2);vector<vector<int>> ret;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(hash[i][j].first&&hash[i][j].second) ret.push_back({i,j});return ret;}int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};void bfs(int i,int j,vector<vector<int>>& heights,int f){f==1?hash[i][j].first=true:hash[i][j].second=true;queue<pair<int,int>> q;q.push({i,j});while(!q.empty()){auto [a,b] = q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&heights[a][b]<=heights[x][y]){if(f==1&&hash[x][y].first) continue;if(f==2&&hash[x][y].second) continue;f==1?hash[x][y].first=true:hash[x][y].second=true;q.push({x,y});}}}}
};

相关文章:

FloodFill算法——搜索算法

一、什么是FloodFill算法 FloodFill算法字面意思就是洪水灌溉法&#xff0c;比如我们有这么一块地&#xff1a; 0表示平原&#xff0c;正数表示高地&#xff0c;负数表示凹地&#xff0c;那么当洪水来临时这些凹地会被优先灌满。而我们要找的正是这些联通块&#xff0c;如&…...

H5接入支付宝手机网站支付并实现

小程序文档 - 支付宝文档中心 1.登录 支付宝开放平台 创建 网页/移动应用 2.填写创建应用信息 3.配置开发设置 4.网页/移动应用&#xff1a;需要手动上线。提交审核后&#xff0c;预计 1 个工作日的审核时间。详细步骤可点击查看 上线应用 。应用上线后&#xff0c;还需要完成…...

基于SpringBoot+uniapp的在线办公小程序+LW示例参考

1.项目介绍 系统角色&#xff1a;管理员、普通用户功能模块&#xff1a;员工管理、部门信息管理、职位信息管理、会议记录、待办事项、工资信息、留言板等技术选型&#xff1a;SpringBoot&#xff0c;Vue&#xff08;后端管理web&#xff09;&#xff0c;uniapp等测试环境&…...

文章精读篇——OMG-LLaVA

题目&#xff1a;OMG-LLaVA: Bridging Image-level, Object-level, Pixel-level Reasoning and Understanding 会议&#xff1a;Conference on Neural Information Processing Systems 2024 论文&#xff1a;http://arxiv.org/abs/2406.19389 主页&#xff1a;https://lxtgh…...

两个同一对象targetList和 sourceList 去重

我现在需要解决的问题是从一个Java的源列表`sourceList`中移除所有在目标列表`targetList`中存在的数据,并且还要去除`targetList`中的重复数据。让我先理清楚这两个问题的思路。 首先,如何快速从`sourceList`中移除含有`targetList`的数据。这里的“含有”应该是指两个列表中…...

软件开发 | GitHub企业版常见问题解读

什么是GitHub企业版&#xff1f; GitHub企业版是一个企业级软件开发平台&#xff0c;专为现代化开发的复杂工作流程而设计。 作为可扩展的平台解决方案&#xff0c;GitHub企业版使组织能够无缝集成其他工具和功能&#xff0c;并根据特定需求定制开发环境&#xff0c;提高整体…...

Docker 网络的配置与管理

目录 查看所有网络 查看网络详细信息 创建新的网络 删除网络 清理未使用的网络 将容器连接到网络 将容器从网络中断开 将容器端口映射到宿主机 绑定到特定 IP 地址 为容器设置自定义 DNS 查看所有网络 docker network ls 功能&#xff1a;列出所有 Docker 网络。 工…...

新手自学:如何用gromacs对简单分子复合物进行伞形采样

1、建立体系: 1、将蛋白的pdb文件转化为gmx: gmx pdb2gmx -f 2BEG_model1_capped.pdb -ignh -ter -o complex.gro 这个网页可以实现将多肽序列转化为pdb: ProBuilder On-line 这个教程的蛋白2BFG包含两条链(chain A和B) 在生成的topol文件中,增加如下的内容,效果就…...

力扣第一题 哈希解法 O(n)时间复杂度

题目&#xff1a; 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那俩个整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案&#xff0c;并且你不能使用两次相同的元素。 你可以按任意顺序返…...

elementui: el-dialog的header设置样式不生效

问&#xff1a; el-dialog的header设置样式不生效 回答&#xff1a; 场景&#xff1a; <el-dialogv-model"dialogVisible"width"800px":before-close"beforeClose"append-to-body:close-on-click-modal"false"title"增加文…...

libpcap 的使用

1.libpcap的模式 有线环境: 使用混杂模式promisous&#xff0c;完成监听无线环境: 使用监听模式monitor&#xff0c;完成监听 2.交叉编译libpcap 设置好交叉编译工具链后下载libpcap源码使用configure进行构建&#xff1a;–disable-shared 构建静态库&#xff0c;–host 、…...

ArcGISPro AA表O_Name字段 内容 复制到BB表BB字段里

import arcpy# 设置工作空间和要处理的表路径 resource_shape_table r"AA表.shp" # 源表路径 resource_assets_table r"BB表.shp" # 目标表路径# 使用 SearchCursor 读取源表中的 O_Name 字段 with arcpy.da.SearchCursor(resource_shape_table, [O_Na…...

2.5 使用注解进行单元测试详解

Mockito 使用注解进行单元测试详解 Mockito 提供了一系列注解来简化测试代码的编写&#xff0c;减少手动创建和管理 Mock 对象的样板代码。结合 JUnit 5&#xff0c;可以更高效地构建清晰、易维护的单元测试。 1. 核心注解概览 注解作用Mock创建并注入一个 Mock 对象&#xf…...

当没有OpenGL时,Skia如何绘制?

Skia 是可以在没有 OpenGL 的情况下进行图形绘制的&#xff0c;但是具体能否成功绘制图形&#xff0c;取决于 Skia 是如何配置的&#xff0c;以及平台上是否提供了其他的底层图形 API。 Skia 的底层依赖 Skia 的目标是提供一种跨平台的 2D 图形绘制接口。为了加速图形渲染&…...

SaaS+AI应用架构:业务场景、智能体、大模型、知识库、传统工具系统

SaaSAI应用架构&#xff1a;业务场景、智能体、大模型、知识库、传统工具系统 大家好&#xff0c;我是汤师爷~ 在SaaS与AI应用的演进过程中&#xff0c;合理的架构设计至关重要。本节将详细介绍其五个核心层次&#xff1a; 业务场景层&#xff1a;发现和确定业务场景智能体层…...

Go 语言中如何高效地处理集合

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons&#xff1a;JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram&#xff0c;自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 &#xff1f; 5 IDEA必装的插件&…...

布隆过滤器到底是什么东西?它有什么用

布隆过滤器&#xff1a;用概率换空间的奇妙数据结构 引言&#xff1a;当空间成为奢侈品 在互联网每天产生2.5万亿字节数据的时代&#xff0c;Google每秒处理超过9万次搜索请求&#xff0c;Redis缓存系统支撑着百万级QPS的访问。面对如此海量的数据处理需求&#xff0c;传统的…...

【数据结构初阶第十节】队列(详解+附源码)

好久不见。。。别不开心了&#xff0c;听听喜欢的歌吧 必须有为成功付出代价的决心&#xff0c;然后想办法付出这个代价。云边有个稻草人-CSDN博客 目录 一、概念和结构 二、队列的实现 Queue.h Queue.c test.c Relaxing Time&#xff01; ————————————《有没…...

沪深300股指期权能对股指期货进行完全套保吗?

锦鲤三三每日分享期权知识&#xff0c;帮助期权新手及时有效地掌握即市趋势与新资讯&#xff01; 沪深300股指期权能对股指期货进行完全套保吗&#xff1f; 沪深300股指期权是以沪深300指数为标的物的期权&#xff0c;而沪深300股指期货则是以该指数作为标的的期货合约。 理…...

JAVA学习第三天

继承关系变量访问的特点 01.方法中找 02.子类变量定义中找 03.父类中找 this和super关键字的使用区别&#xff1a; super父类构造函数的使用&#xff1a; 使用子类构造函数时&#xff0c;都会初始化父类的数据&#xff0c;自动调用父类的无参构造函数 super内存图——007 继…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...