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

【经典算法】BFS_FloodFill算法

目录

  • 1, 算法介绍
  • 2,算法原理和代码实现(含题目链接)
    • 733.图像渲染
    • 200.岛屿的数量
    • 695.岛屿的最大面积
    • 130.被围绕的区域
  • 3, 算法总结

1, 算法介绍

FloodFill(洪水灌溉) 算法介绍

假设一个 4 * 4 的方格代表一块土地,土地上有些地方是凹陷的(假设用负数表示,-1,-2,-3……大小表示凹陷程度),有些地方是凸起的(假设用正数表示,1,2,3,4……大小表示凸起程度)

此时如果发洪水或是下雨,就会把凹陷的地方填满水,凸起的部分就会把凹陷的部分包围,填满水的区域会被连成一片一片的。

所以这类问题要么是问有多少块填平的区域,要么是问最大的区域面积是多少,要么是问某一块区域的边长是多少
在这里插入图片描述

有些问题是规定只能上下左右联通,有些是斜对角也能联通

本质就是找出具有相同性质的联通块。

解决方法:
dfs :深度优先遍历(使用递归)
bfs:宽度优先遍历(层序遍历)

2,算法原理和代码实现(含题目链接)

733.图像渲染

在这里插入图片描述
在这里插入图片描述

算法原理:

使用队列进行层序遍历(bfs)首先要记录原坐标的像素值,再以这个坐标为中心,上下左右四个方向进行遍历,如果发现有相等的像素值,就把这个坐标入队列并且修改成指定的像素值。接着再取出队头元素,进行判断,修改,遍历四个方向,入队列…直到队列为空,此时就把图中所有等于原像素值的位置修改成了指定的像素值

细节/技巧问题:

(1) 记录完原坐标的像素值时,先进行一次判断,是否等于要修改的值,如果是,就直接返回图像

(2) 要得到上下左右四个方向的坐标有技巧
在这里插入图片描述

(3) 要注意遍历四个方向时坐标不能越界

代码实现:

class Solution 
{typedef pair<int, int> PII;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int prev = image[sr][sc];if(prev == color) return image; // 处理特殊情况int m = image.size();int n = image[0].size();queue<PII> q;q.push({sr ,sc});while(q.size()){auto [a, b] = q.front();q.pop();if(image[a][b] == prev) image[a][b] = color;// 判断上下左右的值for(int i = 0; i < 4; i++){int x = a + dx[i];int y = b + dy[i];if(x >=0 && x < m && y >=0 && y < n && image[x][y] == prev)q.push({x, y});}}return image;}
};

200.岛屿的数量

在这里插入图片描述
在这里插入图片描述

算法原理:

这道题就是第一道题的进阶版,也是使用队列层序遍历(bfs),只不过是多次使用bfs算法,所以把它写成一个函数,bfs在这里的作用是标记陆地。遍历整个矩阵,当遇到陆地(‘1’)并且没有被遍历过时,使用bfs并岛屿数量+1

细节/技巧问题:
(1) 当取出队头坐标进行上下左右遍历时,一定会遍历到相同的位置,此时就要进行区分。可以定义一个bool类型的标记数组vis,如果位置已经遍历过,置为true,否则为false

(2) 给bfs函数进行传参时,如果想要形参简洁一些,可以把一些变量定义在main函数外变为公有的,这样可以减少麻烦。比如这道题里矩阵的行和列,标记数组vis等

代码实现:

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n;bool vis[301][301]; // 记录位置有没有被遍历过,true有,false没有
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0; //记录岛屿数量// 遍历整个网格for(int i = 0;i < m; i++){for(int j = 0;j < n; j++){// 如果是陆地并且没有遍历过if(grid[i][j] == '1' && !vis[i][j]){// 把这块陆地标记bfs( grid,i, j);ret++;}}}   return ret;}void bfs(vector<vector<char>>& grid, int i, int j){queue<pair<int ,int>> q;q.push({i, j});vis[i][j] = true; // 入队列代表你已经遍历过了,要标记while(q.size()){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 < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y]){q.push({x,y});vis[x][y] = true;}}}}
};

695.岛屿的最大面积

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法原理:

这道题也是基于前两题的bfs算法,也要多次使用bfs,所以也写成函数。它的作用是标记陆地并且统计每块陆地的面积。遍历矩阵,当遇到没有被遍历过的陆地(1)时,调用bfs函数进行标记与统计,遇到符合要求的坐标并且入队列后,陆地面积+1。统计完每一块陆地的面积再返回给main函数

细节/技巧问题:

参考前面两题

代码实现:

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[51][51];int m,n;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret_max = 0;int ret = 0;for(int i = 0;i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1 && !vis[i][j]){ret = bfs(grid, i, j);ret_max = max(ret, ret_max);}}}return ret_max;}int bfs(vector<vector<int>>& grid, int i, int j){int ret = 0; // 记录岛屿面积queue<pair<int ,int>> q;q.push({i, j});vis[i][j] = true; // 记得标记ret++;while(q.size()){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 < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){q.push({x, y});vis[x][y] = true;ret++;}}}return ret;}
};

130.被围绕的区域

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
算法原理:

这道题也是bfs算法的综合运用。如果按照题意正面去解决,就是直接把除与边界’O’(包括边界)联通的区域外,其余全部修改为’X’,会显的很麻烦。所以正难则反,我们可以先把与边界’O’(包括边界)联通的区域修改为其他字符,再遍历整个数组,把剩余的’O’区域修改为’X’,最后把原来修改为的其他字符还原为’O’,这样也可以解决问题,并且整个代码书写也更清晰。当然,这里的bfs算法也不止使用一次,所以也要写成函数,它的作用是把与边界’O’(包括边界)联通的区域修改为其他字符

细节/技巧问题:

参考前面三题

代码实现:

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m, n;bool vis[201][201];
public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();// 先把边界上的'O'区域改为无关字符for(int i = 0; i < m; i++){if(board[i][0] == 'O') bfs(board, i, 0);if(board[i][n-1] == 'O') bfs(board, i, n-1);}for(int j = 0; j < n; j++){if(board[0][j] == 'O') bfs(board, 0, j);if(board[m-1][j] == 'O') bfs(board, m-1, j);}// 再遍历矩阵,把所有'O'改为'X'for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'O' && !vis[i][j])board[i][j] = 'X';}}// 最后还要把前面改过的'.'还原为'O'for(int i = 0; i< m; i++){for(int j = 0; j < n; j++)if(board[i][j] == '.')board[i][j] = 'O';}}void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int ,int>> q;q.push({i ,j});vis[i][j] = true;board[i][j] = '.';while(q.size()){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 < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == 'O'){q.push({x, y});vis[x][y] = true;board[x][y] = '.';}}}}
};

3, 算法总结

bfs是一种十分经典的算法,它总是使用队列来完成层序遍历,其实就是以当前位置为中心,再进行上下左右四个方向的位置识别,查找与统计。通过前面四道题的介绍,我们也可以发现bfs算法也是有大致的固定模版,只不过每个bfs算法在解决问题的过程中的作用不同而已

相关文章:

【经典算法】BFS_FloodFill算法

目录 1&#xff0c; 算法介绍2&#xff0c;算法原理和代码实现(含题目链接)733.图像渲染200.岛屿的数量695.岛屿的最大面积130.被围绕的区域 3&#xff0c; 算法总结 1&#xff0c; 算法介绍 FloodFill(洪水灌溉) 算法介绍&#xff1a; 假设一个 4 * 4 的方格代表一块土地&am…...

RocketMQ之Topic主题详解

Topic概念定义 主题&#xff1a;RocketMQ中消息传输和存储的顶层容器&#xff0c;用于标识同类业务中逻辑的消息&#xff0c;可理解为消息的分类&#xff0c;主题消息的分类取决于业务&#xff0c;要发送的业务消息最好单独是一个Topic主题&#xff0c;以保证互相不被干扰Topi…...

实战OpenCV之图像显示

基础入门 OpenCV提供的功能非常多&#xff0c;图像显示是最基础也是最直观的一部分。它让我们能够直观地看到算法处理后的效果&#xff0c;对于调试和验证都至关重要。在OpenCV中&#xff0c;图像显示主要依赖于以下四个关键的数据结构和函数。 1、Mat类。这是OpenCV中最基本的…...

I2C的10-bit地址空间

10-bit地址空间&#xff1a; I2C支持 10-bit的设备地址&#xff0c;此时的时序如下图所示&#xff1a; 在 10-bit地址的 I2C系统中&#xff0c;需要两个帧来传输 slave的地址。第一个帧的前 5个 bit固定为 b11110&#xff0c;后接 slave地址的高 2位&#xff0c;第 8位仍然是 …...

TinyWebserver的复现与改进(6):定时器处理非活动连接

如果客户端长时间没有动作&#xff0c;会占用了许多连接资源&#xff0c;严重影响服务器的性能。因此需要通过实现一个服务器定时器&#xff0c;处理这种非活跃连接&#xff0c;释放连接资源。 定时器处理流程 SIGALARM触发&#xff1a;整个流程开始于一个 SIGALARM 信号&…...

ThinkPHP5 5.0.23 远程代码执行漏洞

目录 1、启动环境 2、漏洞利用 3、更改传参方式 4、修改参数 5、发送数据 1、启动环境 docker-compose up -d 2、访问靶机ip端口号8080 2、漏洞利用 使用burpsuite抓包软件抓包 3、更改传参方式 将 GET传参改为POST传参 4、修改参数 url参数 /index.php?scaptcha post参…...

C++鼠标键盘操作自动化

C鼠标键盘操作自动化 #pragma once #include <Windows.h> enum KEYS{A 65,W87,S83,D68,SHIFTVK_LSHIFT,ALT18,Tilde 126,//~TABVK_TAB,B66,SPACEVK_SPACE,ESCVK_ESCAPE,Q81 }; enum MOUSE {ML,MW,MR//左&#xff0c;中&#xff0c;右 }; class simulator//模拟器 { pu…...

多个主流Python GUI库全面解析,助你用Python轻松构建精美界面

Python 作为一门易学易用的编程语言&#xff0c;在各个领域都拥有广泛的应用。而 GUI (Graphical User Interface) 编程更是让 Python 变得更加灵活&#xff0c;可以帮助我们创建各种各样的桌面应用&#xff0c;为用户提供直观的交互体验。本文将介绍几个Python GUI 编程中常用…...

Kotlin学习-01创建kotlin学习

安装idea https://www.jetbrains.com/zh-cn/ 创建项目 选择kotlin 修改Main.kt fun main() {print("Hello World!") }运行...

Java、python、php版的企业单位考勤打卡管理系统的设计与实现(源码、调试、LW、开题、PPT)

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人 八年开发经验&#xff0c;擅长Java、Python、PHP、.NET、Node.js、Android、微信小程序、爬虫、大数据、机器学习等&#xff0c;大家有这一块的问题可以一起交流&…...

在IntelliJ IDEA中使用Git推送项目

去gitee网站注册用户 gitee网站地址:https://gitee.com/ github网站地址:https://github.com/ 一、创建仓库 以下以gitee为例进行介绍&#xff0c;github操作雷同。 1、创建仓库 点击页面右上方的"“并选择"创建仓库” 2、设置仓库相关信息 首先输入仓库名&…...

CNN代码实战

CNN的原理 从 DNN 到 CNN &#xff08;1&#xff09;卷积层与汇聚 ⚫ 深度神经网络 DNN 中&#xff0c;相邻层的所有神经元之间都有连接&#xff0c;这叫全连接&#xff1b;卷积神经网络 CNN 中&#xff0c;新增了卷积层&#xff08;Convolution&#xff09;与汇聚&#xff08…...

迁移学习代码复现

一、前言 说来可能令人难以置信,迁移学习技术在实践中是非常简单的,我们仅需要保留训练好的神经网络整体或者部分网络,再在使用迁移学习的情况下把保留的模型重新加载到内存中,就完成了迁移的过程。之后,我们就可以像训练普通神经网络那样训练迁移过来的神经网络了。 我们…...

Elasticsearch(ES)常用命令

常用运维命令 一、基本命令1.1、查看集群的健康状态1.2、查看节点信息1.3、查看索引列表1.4、创建索引1.5、删除索引1.6、关闭索引1.7、打开索引1.8、查看集群资源使用情况&#xff08;各个节点的状态&#xff0c;包括磁盘&#xff0c;heap&#xff0c;ram的使用情况&#xff0…...

C/C++ 不定参函数

C语言不定参函数 函数用法总结 Va_list 作用&#xff1a;类型定义&#xff0c;生命一个变量&#xff0c;该变量被用来访问传递给不定参函数的可变参数列表用法&#xff1a;供后续函数进调用&#xff0c;通过该变量访问参数列表 typedefchar* va_list; va_start 作用&#xff…...

C语言——函数专题

1.概念 在C语言中引入函数的概念&#xff0c;有些翻译为子程序。C语言中的函数就是一个完成某项特定任务的一小段代码&#xff0c;这个代码是有特殊的写法和调用方法的。一般我们可以分为两种函数&#xff1a;库函数和自定义函数。 2.库函数 C语言国际标准ANSIC规定了一些常…...

springboot打可执行jar包

1. pom文件如下 <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"><m…...

【SQL】科目种类

目录 题目 分析 代码 题目 表: Teacher ------------------- | Column Name | Type | ------------------- | teacher_id | int | | subject_id | int | | dept_id | int | ------------------- 在 SQL 中&#xff0c;(subject_id, dept_id) 是该表的主键。 该表…...

【深度学习】【语音】TTS,最新TTS模型概览,扩散模型TTS,MeloTTS、StyleTTS2、Matcha-TTS

文章目录 基础介绍对比基础介绍 MeloTTS: MeloTTS 是 MyShell.ai 开发的一个多语言语音合成模型,支持包括英语、西班牙语、法语、中文、日语和韩语等多种语言。它以高质量的语音合成为特色,尤其擅长处理中英混合内容。该模型优化了在 CPU 上的实时推理能力,使其在多种应用场…...

【论文笔记】LION: Linear Group RNN for 3D Object Detection in Point Clouds

原文链接&#xff1a;https://arxiv.org/abs/2407.18232 简介&#xff1a;Transformer在3D点云感知任务中有二次复杂度&#xff0c;难以进行长距离关系建模。线性RNN则计算复杂度较低&#xff0c;适合进行长距离关系建模。本文提出基于窗口的网络线性组RNN&#xff08;即对分组…...

打造高可用集群的基石:深度解析Keepalived实践与优化

高可用集群 集群类型 集群类型主要分为负载均衡集群&#xff08;LB&#xff09;、高可用集群&#xff08;HA&#xff09;和高性能计算集群&#xff08;HPC&#xff09;三大类。每种集群类型都有其特定的应用场景和优势。 1. 负载均衡集群&#xff08;LB&#xff09; 负载均衡集…...

Web大学生网页作业成品——环保主题介绍网页网站设计与实现(HTML+CSS)(5个页面)

&#x1f389;&#x1f389;&#x1f389; 常见网页设计作业题材有**汽车、环保、明星、文化、国家、抗疫、景点、人物、体育、植物、公益、图书、节日、游戏、商城、旅游、家乡、学校、电影、动漫、非遗、动物、个人、企业、美食、婚纱、其他**等网页设计题目, 可满足大学生网…...

Qt登录窗口设计

widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QIcon> //图标类 #include <QPushButton> #include <QLineEdit> //行编辑 #include <QLabel> #include <QTextEdit> #include <QMovie>class Widge…...

探索数据矿藏:我的AI大模型与数据挖掘实战经验分享

&#x1f680; 探索数据矿藏&#xff1a;我的AI大模型与数据挖掘实战经验分享 &#x1f496; 前言&#xff1a;数据的金矿&#xff0c;AI的翅膀 在人工智能的浪潮中&#xff0c;我有幸作为项目负责人&#xff0c;带领团队深入挖掘数据的潜力&#xff0c;利用AI大模型的力量&am…...

linux C语言strcat函数及相关函数

讯飞星火 strcat函数是C语言中的一个字符串处理函数,用于将一个字符串追加到另一个字符串的末尾。它的原型如下: char *strcat(char *dest, const char *src);参数说明: dest:目标字符串,即要将src字符串追加到这个字符串的末尾。src:源字符串,即要追加到dest字符串末…...

使用 sort 进行文本文件处理

sort 使用经验笔记 一、简介 sort 是一个命令行工具&#xff0c;用于对文本文件中的行进行排序。它广泛应用于 Unix/Linux 系统中&#xff0c;可以用来对文件的内容进行简单的排序操作&#xff0c;也可以与其他命令结合使用来完成更复杂的任务。 二、基本用法 排序文件: sor…...

HarmonyOS笔记4:从云数据库获取数据

移动应用获取数据的方式主要有&#xff1a; 1.从网络中获取数据接口API。 2.从华为云数据库获取云数据库的资源。 3.从移动终端直接获取本地的数据 在HarmonyOS笔记3中已经完成了方式一从网络中获取数据接口API的方式。在本篇笔记中&#xff0c;将讨论从云数据库中获取数据。 因…...

QT5生成独立运行的exe文件

目录 1 生成独立运行的exe文件1.1 设置工程Release版本可执行文件存储路径1.2 将工程编译成Release版本 2 使用QT5自带的windeployqt拷贝软件运行依赖项3 将程序打包成一个独立的可执行软件exe4 解决QT5 This application failed to start because no Qt platform plugin could…...

LabVIEW光纤水听器闭环系统

开发了一种利用LabVIEW软件开发的干涉型光纤水听器闭环工作点控制系统。该系统通过调节光源频率和非平衡干涉仪的光程差&#xff0c;实现了工作点的精确控制&#xff0c;从而提高系统的稳定性和检测精度&#xff0c;避免了使用压电陶瓷&#xff0c;使操作更加简便。 项目背景 …...

Shell——流程控制语句(if、case、for、while等)

在 Shell 编程中&#xff0c;流程控制语句用于控制脚本的执行顺序和逻辑。这些语句包括 if、case、for、while 等&#xff0c;它们的使用可以使脚本实现更复杂的逻辑。以下是它们的详细说明和语法结构&#xff1a; 1. if 语句 if 语句用于条件判断&#xff0c;执行符合条件的…...