【基础算法总结】BFS 解决 FloodFill 算法

BFS 解决 FloodFill 算法

  • 1.图像渲染
  • 2.岛屿数量
  • 3.岛屿的最大面积
  • 4.被围绕的区域

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

FloodFill 算法 就是在一个矩阵中找性质相同的连通块。关于这个在《递归、搜索回溯专题》 有详细介绍。并且用的是DFS解决问题,这里主要是用BFS解决FloodFill 算法。

1.图像渲染

题目链接:733. 图像渲染

题目分析:

在这里插入图片描述

这道题的意思是,给一个开始位置,把和它性质相同的连通块都找到,并且渲染成color。注意可以上下左右四个方向去找。

算法原理:

解法:BFS

BFS(宽度优先遍历/宽度优先搜索/层序遍历),借助队列实现,一层一层出。
起始位置先入队。队列不空出队,把它上下左右和它颜色相同的放入队列。然后循环下去,直到队列为空。

在这里插入图片描述

class Solution 
{//处理数对,经常用到pair,可以typedef一下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) {       if(image[sr][sc] == color) return image;//处理边界情况int prev = image[sr][sc];//先标记一下需要修改的像素值int m = image.size(), n = image[0].size();queue<PII> q;q.push({sr,sc});while(q.size()){//first -> a, second -> bauto [a,b] = q.front();q.pop();image[a][b] = color;//上下左右四个方向for(int i = 0; i < 4; ++i){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){q.push({x,y});}}}return image;}
};

2.岛屿数量

题目链接:200. 岛屿数量

题目描述:

在这里插入图片描述

求岛屿的数量,每座岛屿只能上下左右去找。

在这里插入图片描述

算法原理:

解法:BFS

从左往右扫描这个矩阵,当遇到陆地的时候就把和陆地相连的岛屿找到,如何找,就是BFS从这个地方宽搜一遍,就可以把连通的区域找到。可以搞一个变量ret 记录陆地数量就可以。但是这里层序遍历有一个问题。从一个位置扩展到下一个位置,不能在从下一个位置在回到上一个位置不然就死循环了。为了避免这种情况我们有两种方式。

  1. 修改原始矩阵的值
  2. 搞一个同等矩阵大小的bool类型的二维数组,记录当前位置是否已经被搜索过,false表示没有,true表示搜索过。并且当前位置bfs一次之后。和它相连的其他岛屿也被置为true,然后从左往右遍历的时候即使它是1,也不会进去了。
class Solution 
{//bool vis[301][301];  //感觉浪费空间就先计算一下当前需要多大空间,然后再申请vector<vector<int>> vis;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m,n;
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();vis.resize(m,vector<int>(n));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);}}}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 && !vis[x][y] && grid[x][y] == '1'){                  q.push({x,y});vis[x][y] = true;}}}}
};

3.岛屿的最大面积

题目链接:695. 岛屿的最大面积

题目分析:

在这里插入图片描述
这道题是求那一个连通块的面积是最大的。

算法原理:

解法:BFS

还是从左往右扫完,当碰到一块土地就去找和这个土地连通的所有土地,如何找?还是用BFS遍历一次,同时要有一个变量count统计这个岛屿面积有多大。注意找过的土地下一次不能在找了!因此我们还是来一个bool类型的二维数组来标记那些土地是已经被搜索过了!搜索过了下一次就不能找了。

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

4.被围绕的区域

题目链接: 130. 被围绕的区域

题目分析:

在这里插入图片描述

把被 ’ X ’ 围绕的 ’ O '区域修改为 ’ X ',被围绕的区域指的是这个区域的 ’ O ’ 没有处于边界。

算法原理:

如下面这张图只有一处区域是要被修改的,此时我们是有两种解法的。

解法一:直接做

从左往右扫描,当遇到 ‘O’ 之后,就把与这个 ‘O’ 相连的 ‘O’ 区域都修改成 ‘X’,这是我们之前做的方式。但是这里有一个问题当我在扫描遇到 ‘O’ 也会把下面绿色区域修改成 ‘X’ ,但是这块区域有 ‘O’ 是处于边界的,因此这一块区域是不能够被修改的!所以在BFS过程中遇到 ‘O’ 处于边界的情况这块是不能被修改的。
在这里插入图片描述
更为极端的例子是,当BFS是把这个区域遍历一遍之后才知道这个区域是不能够被修改的,还要把已经被修改过成 ‘X’ 还原成 ‘O’。但是我们BFS是一边修改一边遍历的。然后遍历到 ‘O’ 处于边界才知道这个区域是不能被修改的,并且刚才修改过的是错的,还要还原回去,但此时前面变成 ‘X’ 的 ‘O’ 特别难被还原回去。

在这里插入图片描述
不过还可以这样,先去BFS遍历一遍看看这个区域是否合法,如果合法在去BFS把这块区域修改成 ‘X’,需要两个BFS。

解法二:正难则反
正着来不太好处理与边界相连的连通块,那就反着来就先处理与边相连的连通块。先遍历四条边界,在四条边界发现有 ‘O’ ,仅对这些边界上的 ‘O’ 来一次BFS,把这个连通块都修改成 ‘.’。这样把处于边界的 ‘O’ 连通快都修改成 '.'之后,接下来仅需遍历一下矩阵,把矩阵中的剩下的 ‘O’ 修改成 ‘X’ ,把 ‘.’ 还原成 'O’就可以了。

  1. 先处理边界上 ‘O’ 区域
  2. 扫描矩阵,还原即可
class Solution {int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;
public:void solve(vector<vector<char>>& board) {m=board.size(),n=board[0].size();// 1.把边界的 O 相连的连通块,全部修改成 .for(int i = 0; i < m; ++i)for (int j = 0; j < n; ++j)if(board[i][j] == 'O')if(i == 0 || i == m-1 || j == 0 || j == n-1) bfs(board,i,j);// 2.还原for(int i = 0; i < m; ++i)for(int j = 0; j < n; ++j){if(board[i][j] == 'O') board[i][j]='X';else 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});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 && board[x][y] == 'O'){q.push({x,y});board[x][y] = '.';}}}}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/397507.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【基础算法总结】BFS 解决最短路径问题

BFS 解决最短路径问题 1.最短路径问题简介2.迷宫中离入口最近的出口3.最小基因变化4.单词接龙4.为高尔夫比赛砍树 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1…

Day17 枚举、typedef、位运算、堆空间的学习

目录 枚举 typedef 位运算 堆上的空间 枚举 一个一个列举出来&#xff0c;是指将变量的值一一列举出来&#xff0c;变量的值只限于列举出来的值的范围内。 作用&#xff1a; 1、为了提高代码的可读性 2、提高代码的安全性 枚举类型 基本语法&#xff1a; enum 枚举名 { …

根据toml编译生成whl

1、安装build pip install build如果已经安装build, 那就执行一下升级命令 python3 -m pip install --upgrade build2、在pyproject.toml所在的文件夹那一层执行 # -w:生成whl文件 -v:显示python编译过程 python3 -m build -w -v2.1 当出现以下输出&#xff0c;需要耐心等待…

Java 集成测试详解及示例

通过综合指南探索 Java 集成测试的世界。了解工具、流程和最佳实践&#xff0c;并辅以实际示例。 随着软件系统变得越来越大、越来越复杂&#xff0c;组件和服务以错综复杂的方式交互&#xff0c;集成测试已变得不可或缺。通过验证所有组件和模块在组合时是否正常工作&#xff…

入门岛2-python实现wordcount并进行云端debug

书生大模型学习 任务&#xff1a; 1.实现一个wordcount函数&#xff0c;统计英文字符串中每个单词出现的次数。返回一个字典&#xff0c;key为单词&#xff0c;value为对应单词出现的次数。 2.Vscode连接InternStudio debug TIPS&#xff1a;记得先去掉标点符号,然后把每个单词…

Mybatis学习-day19

Mybatis学习-day19 1. resultMap resultMap 是 MyBatis 中最复杂的元素&#xff0c;主要用于解决实体类属性名与数据库表中字段名不一致的情况&#xff0c;可以将查询结果映射成实体对象。 <resultMap id"staffAndDep" type"com.easy.bean.Staff">…

解決android Studio在导入已有的工程 build 时出现的错误

最近在学习andriod方面的知识&#xff0c;第一次使用android Studio导入别人的项目&#xff0c;从导入到build出现了几个问题&#xff0c;在这里记录以下解决过程。 SDK location not found 如下图报错所示&#xff0c;看网上教程有的说是SDK未安装&#xff0c;这里我是明确自…

两个AI关小黑屋:Llama3.1把Claude Opus聊自闭了

把Llama 3.1 405B和Claude 3超大杯Opus双双送进小黑屋&#xff0c;你猜怎么着—— Llama把Claude整得精神崩溃了&#xff0c;Claude明确拒绝继续聊天&#xff0c;还要再被Llama PUA的那种。 在一场AI和AI对话的安全词模拟实验中&#xff0c;X上的这位人类监督者记录下了一出好…

【HarmonyOS NEXT星河版开发学习】小型测试案例12-点赞案例

个人主页→VON 收录专栏→鸿蒙开发小型案例总结​​​​​ 基础语法部分会发布于github 和 gitee上面&#xff08;暂未发布&#xff09; 前言 本案例主要运用了交互点击事件和基础的算术运算符的应用&#xff0c;难度并不大&#xff0c;卡片的制作相对来说并不是太难&#xff0…

机器学习/深度学习——模型的欠拟合和过拟合,正则化方法详解

机器学习/深度学习——模型的欠拟合和过拟合&#xff0c;正则化方法 详解 搭配以下文章进行学习&#xff1a; 卷积神经网络&#xff1a; 深度学习——卷积神经网络&#xff08;convolutional neural network&#xff09;CNN详解&#xff08;一&#xff09;——概述. 步骤清晰…

深度解析HAProxy:构建高可用负载均衡的终极指南

目录 haproxy配置文件组成 实验环境 haproxy安装 haproxy的配置文件说明 全局配置段global 多进程和多线程配置 代理配置段proxies server配置说明 实验相关配置 测试效果&#xff1a; haproxy的状态页 socat命令 socat命令的一些常用示例 HAProxy的调度算法 静…

网鼎杯-2018-Web-Unfinish

先尝试万能注入&#xff1a; 如果万能注入缺少符号&#xff0c;如果加符又进不去&#xff0c;那我们尝试扫描文件,然后发现有一个register.php的文件&#xff0c;应该是注册页面&#xff0c;我们去打开 知道存储的文件&#xff0c;并利用状态码进行过滤 我们注册的用户名就是aa…

【Redis 进阶】集群(重点理解流程和原理)

一、基本概念 前面学习的哨兵模式&#xff0c;提高了系统的可用性。但是真正用来存储数据的还是 master 和 slave 节点&#xff0c;所有的数据都需要存储在单个 master 和 slave 节点中。如果数据量很大&#xff0c;接近超出了 master / slave 所在机器的物理内存&#xff0c…

【数据结构详解】——冒泡排序(动图详解)

目录 &#x1f552; 1. 冒泡排序 &#x1f552; 1. 冒泡排序 &#x1f4a1; 算法思想&#xff1a;两两比较相邻记录的关键字&#xff0c;如果反序则交换&#xff0c;直到没有反序的记录为止。一共进行n-1趟这样的交换将可以把所有的元素排好。 代码实现如下&#xff1a; voi…

uniapp点击图片预览,关闭预览图片后自动触发onshow生命周期,怎么解决?

第一&#xff0c;页面的数据会实时更新&#xff0c;所以接口请求需要在onshow中&#xff0c;变量figh初始为true&#xff0c;数据列表信息可直接调用获取 当点击查看图片时改变&#xff0c;变量figh为false&#xff0c;此时onshow里面的this.postlist()不触发。 此时&#xff0…

国产大模型市场遇冷:挑战与机遇并存,一般人学大模型,我劝你算了吧

前阵子&#xff0c;大模型赛道非常热闹&#xff0c;360、字节、KIMI、知乎等公司纷纷召开发布会&#xff0c;推出自己独具特色的新产品&#xff0c;一时间引发市场的不少想象和讨论。在看似百花齐放、万紫千红的同时&#xff0c;K哥也观察到了一些不好的迹象&#xff0c;这些“…

【软件测试】功能测试理论基础

目录 项目的测试流程&#x1f3f4; 需求评审 评审形式 测试人员在需求评审中职责 测试计划与方案 测试计划 问题 测试方案&#x1f3f4; 测试计划与方案的对比 功能测试设计&#x1f3f4; 测试设计的步骤 项目的测试流程&#x1f3f4; 作用&#xff1a; 有序有效开展…

力扣Hot100-994腐烂的橘子

中等 在给定的 m x n 网格 grid 中&#xff0c;每个单元格可以有以下三个值之一&#xff1a; 值 0 代表空单元格&#xff1b;值 1 代表新鲜橘子&#xff1b;值 2 代表腐烂的橘子。 每分钟&#xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格…

MiniCPM-V: A GPT-4V Level MLLM on Your Phone 手机上的 GPT-4V 级多模态大模型

GitHub - OpenBMB/MiniCPM-V: MiniCPM-V 2.6: A GPT-4V Level MLLM for Single Image, Multi Image and Video on Your Phone 2408.01800 (arxiv.org) 目录 Introduction Model Architecture Training End-side Deployment MiniCPM-V是一种高效的多模态大型语言模型&…

cad文字转arcgis注记

cad中文字转为arcgis注记&#xff0c;步骤如下&#xff1a; 1、将dwg文件下annotation文件加到图层中 2、文件点击右键&#xff0c;转换地理数据库注记 3、 导入默认地理数据库中&#xff0c;或自己新建地理数据库&#xff0c;起个文件名、点确定&#xff08;注意&#xff1a…