初识 Floodfall 算法
文章目录
- **一、Floodfall 算法的概述**
- **二、深度优先搜索(DFS)和广度优先搜索(BFS)在 Floodfall 算法中的应用**
- **三、算法的基本原理**
- **四、应用场景**
一、Floodfall 算法的概述
Floodfall 算法通常用于解决与区域填充、图的遍历等相关的问题。它的中文名字:洪水灌溉,顾名思义它的核心思想是从一个起始点开始,像洪水一样蔓延,直到满足特定的条件或覆盖整个目标区域。
Floodfall 算法在实现过程中,常常会基于深度优先搜索(DFS)和广度优先搜索(BFS)的思想。
二、深度优先搜索(DFS)和广度优先搜索(BFS)在 Floodfall 算法中的应用
深度优先搜索(DFS)在 Floodfall 算法中,会沿着一条路径尽可能深地探索下去,直到无法继续,然后回溯。这种方式在某些情况下能够快速找到较深的区域,但可能会忽略一些较近但隐藏较深的区域。
例如,在一个迷宫中,如果使用 DFS 进行 Floodfall 式的探索,可能会先深入一条复杂的长通道,而错过一些就在入口附近但需要绕一点路才能到达的区域。
广度优先搜索(BFS)则是逐层地向外扩展,先访问距离起始点近的节点,再逐步扩展到更远的节点。在 Floodfall 算法中,BFS 能确保先填充距离起始点较近的区域,填充的顺序更加有序和可预测。
比如在地图填充中,使用 BFS 进行 Floodfall 操作,会先填充起始点周围的区域,再逐渐向外扩散。
三、算法的基本原理
Floodfall 算法一般会使用某种数据结构(如队列或栈)来存储待处理的节点。从起始节点出发,将其相邻的未访问节点加入数据结构,然后依次处理这些节点,不断扩展填充区域。
四、应用场景
- 图像处理中的颜色填充。
- 游戏地图中的区域探索。
下面是一个使用 C++实现的简单 Floodfall 算法示例代码,用于填充二维矩阵中的一个区域,分别展示了基于 DFS 和 BFS 的实现方式:
#include <iostream>
#include <stack>
#include <queue>// 定义矩阵的大小
const int ROWS = 10;
const int COLS = 10;// 方向数组,用于遍历相邻节点
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };// 定义一个结构体来表示节点
struct Node {int x;int y;
};// 基于 DFS 的 FloodFill 函数
void floodFillDFS(int grid[ROWS][COLS], int startX, int startY, int targetColor, int newColor) {std::stack<Node> s;Node start;start.x = startX;start.y = startY;s.push(start);while (!s.empty()) {Node curr = s.top();s.pop();int x = curr.x;int y = curr.y;// 如果当前节点的颜色与目标颜色不同,跳过if (grid[x][y]!= targetColor) {continue;}// 更改颜色grid[x][y] = newColor;// 遍历相邻节点for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查边界if (newX >= 0 && newX < ROWS && newY >= 0 && newY < COLS) {Node next;next.x = newX;next.y = newY;s.push(next);}}}
}// 基于 BFS 的 FloodFill 函数
void floodFillBFS(int grid[ROWS][COLS], int startX, int startY, int targetColor, int newColor) {std::queue<Node> q;Node start;start.x = startX;start.y = startY;q.push(start);while (!q.empty()) {Node curr = q.front();q.pop();int x = curr.x;int y = curr.y;// 如果当前节点的颜色与目标颜色不同,跳过if (grid[x][y]!= targetColor) {continue;}// 更改颜色grid[x][y] = newColor;// 遍历相邻节点for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查边界if (newX >= 0 && newX < ROWS && newY >= 0 && newY < COLS) {Node next;next.x = newX;next.y = newY;q.push(next);}}}
}// 打印矩阵
void printGrid(int grid[ROWS][COLS]) {for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {std::cout << grid[i][j] << " ";}std::cout << std::endl;}
}int main() {int grid[ROWS][COLS] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},{0, 1, 0, 0, 0, 0, 0, 0, 1, 0},{0, 1, 0, 1, 1, 1, 1, 0, 1, 0},{0, 1, 0, 1, 0, 0, 1, 0, 1, 0},{0, 1, 0, 1, 0, 0, 1, 0, 1, 0},{0, 1, 0, 1, 1, 1, 1, 0, 1, 0},{0, 1, 0, 0, 0, 0, 0, 0, 1, 0},{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};std::cout << "原始矩阵:" << std::endl;printGrid(grid);std::cout << "基于 DFS 填充后的矩阵:" << std::endl;floodFillDFS(grid, 1, 1, 1, 2);printGrid(grid);std::cout << "基于 BFS 填充后的矩阵:" << std::endl;floodFillBFS(grid, 1, 1, 2, 3);printGrid(grid);return 0;
}
在上述代码中,我们分别实现了基于 DFS 和 BFS 的 Floodfall 算法,用于填充二维矩阵中的指定区域。
相关文章:
初识 Floodfall 算法
文章目录 **一、Floodfall 算法的概述****二、深度优先搜索(DFS)和广度优先搜索(BFS)在 Floodfall 算法中的应用****三、算法的基本原理****四、应用场景** 一、Floodfall 算法的概述 Floodfall 算法通常用于解决与区域填充、图的…...
[Linux] LVM挂载的硬盘重启就掉的问题解决
问题:系统重启后挂在逻辑卷的盘会掉(必现) 环境:SUSE Linux 11 SP4 原因:boot.lvm是关闭的 解决:boot.lvm设置开启 参考资料: linux下lvm状态Not avaliable问题排查及处理(常见Suse操作系统…...
YOLOv8改进 | 主干网络 | 用EfficientNet卷积替换backbone【教程+代码 】
秋招面试专栏推荐 :深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 💡💡💡本专栏所有程序均经过测试,可成功执行💡💡💡 专栏目录 :《YOLOv8改进有效涨点》专栏介绍 & 专栏目录 | 目前已有80+篇内容,内含各种Head检测头、损失函数Loss、…...
数据库规范化设计 5大基本原则
规范化设计原则是数据库设计的基本原则,有助于减少数据冗余,提高数据一致性和完整性,简化数据管理,增强数据安全性,对整个开发项目至关重要。而缺乏规范化设计会导致数据冗余,增加存储成本,引发…...
【nginx】解决k8s中部署nginx转发不会自动更新域名解析启动失败的问题
文章目录 1. 问题2.解决办法3.扩展说明3.1 DNS解析阶段划分3.2 问题说明3.2.1 先看/etc/resolv.conf说明3.2.2 针对第一个问题3.2.3 针对第二个问题 【后端】NginxluaOpenResty高性能实践 参考: https://blog.csdn.net/u010837612/article/details/123275026 1. 问…...
LeetCode637 二叉树的层平均值
前言 题目: 637. 二叉树的层平均值 文档: 代码随想录——二叉树的层平均值 编程语言: C 解题状态: 求取平均值的时候出现了点问题 思路 C中,浮点数的相加会产生精度误差,求取平均值时最好只在最后一步进行…...
王学岗ASM
服务发现 package com.example.testasm;import android.content.Context; import android.os.Bundle;import androidx.activity.EdgeToEdge; import androidx.appcompat.app.AppCompatActivity; import androidx.core.graphics.Insets; import androidx.core.view.ViewCompat;…...
【数据结构】—— 队列
1、队列的概念2、队列的结构如何选择合适的数据结构实现队列(数组or链表) 3、队列的链式存储3.1 队列的链式存储结构3.2 队列的常见接口3.3 队列的接口实现初始化判空入队列出队列获取队头元素获取队尾元素获取节点个数销毁 3.4 源代码 4、队列的顺序存储…...
vue中openlayers过滤高亮显示某个图层
vue中openlayers过滤高亮显示某个图层 openlayers库没有直接支持这样设置,所以可以使用库:ol-ext,地址:https://viglino.github.io/ol-ext/examples/filter/map.filter.crop.html 效果: 关键代码: /**…...
WPF篇(11)-ToolTip控件(提示工具)+Popup弹出窗口
ToolTip控件 ToolTip控件继承于ContentControl,它不能有逻辑或视觉父级,意思是说它不能以控件的形式实例化,它必须依附于某个控件。因为它的功能被设计成提示信息,当鼠标移动到某个控件上方时,悬停一会儿,…...
【mysql 第一篇章】系统和数据库的交互方法
一、宏观的查看系统怎么和数据库交互 在我们刚刚接触系统和数据库的时候不明白其中的原理,只知道系统和数据库是需要交互的。所以我们会理解成上图的形式。 二、MYSQL 驱动 随着我们的学习时间的加长以及对程序的了解,发现链接数据库是需要有别的工具辅…...
数据结构-位运算总结
位运算总结: 1.求位1的个数 191. 位1的个数 - 力扣(LeetCode) 有两种写法: 1.是把该数不断的去与0x1相与,得到该数的最后一位的值,然后判断他是不是1,再把该数更新一下整体往后移动一位也就…...
java 异常堆栈的由来
编写的程序代码内部错误产生的异常,如调用对象为空(空指针异常)、数组越界异常、除0异常等。这种通常称为未检查的异常(Runtime异常子类),在虚拟机中执行时会集中处理这些异常。其他运行中异常,通过throw语句主动抛出的…...
【推荐系统】【多任务学习】Progressive Layered Extraction (PLE)
Progressive Layered Extraction (PLE): A Novel Multi-Task Learning (MTL) Model for Personalized Recommendations 文章目录 Progressive Layered Extraction (PLE): A Novel Multi-Task Learning (MTL) Model for Personalized Recommendations1 论文出处2 背景2.1 背景介…...
java -转win32/win64免安装jre环境运行
由于java 转为exe,只能在装有JDK环境的电脑运行, 发给其他人也不能运行,缺少环境,程序自己背着jre走 1.先打好jar 包 2.使用exe4j 把jar包转成exe 运行程序 3.使用inno stup ,把exe运行程序加上jre环境 以下是具体实现…...
算法板子:容斥原理——求出 1∼n 中能被质数 p1,p2,…,pm 中的至少一个数整除的整数有多少个
1. 题目要点 1. 设:求1~10中能被质数2和3中至少一个数整除的数有多少个。1~10中能被质数2整除的数的集合记为S1{2,4,6,8,10},能被质数3整除的数的集合记为S2{3,6,9},能同时被质数2和3整数的数的集合为S1∩S2{6} 2. 这道题的目的是求S1∪S2∪S…...
用gurobipy求解带不等式约束条件的优化问题
1. 引入 在当今的数据驱动世界中,优化问题无处不在,从工程设计到经济模型,再到机器学习算法的调参,优化都是实现效率最大化、成本最小化或性能最优化的关键工具。 这里有一个典型的数学优化问题,目标是在给定的约束条…...
漏洞复现-Adobe ColdFusion 远程代码执行漏洞(CVE-2023-38203)
1.漏洞描述 Adobe ColdFusion是一种服务器端的Web应用开发平台。它由Adobe Systems开发,用于创建动态的、交互式的Web应用程序和网站。 Adobe ColdFusion在2018u17及之前版本、2021u7及之前版本和2023u1及之前版本中存在任意代码执行漏洞。该漏洞是由于反序列化不…...
Spring-MyBatis整合:No qualifying bean of type ‘XXX‘ available: ...
1.看一下核心配置中有没有导入myBatis配置 2.看一下service和dao有没有相应注解 3.看一下MyBatisConfig中有没有对sqlSessionFactory和mapperScannerConfigurer注释成bean对象以及有没有配置映射文件路径...
gitea docker 快捷安装部署
前言 在前一篇博文(什么是 Gitea?)中,我们详细介绍了gitea的功能特性,以及其与其它git服务器之间的特性多维度对比。 在本文中,我们将详细介绍gitea的快捷安装部署,docker方式! 1…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
