算法学习系列(四十一):Flood Fill算法

2024-03-19 15:36

本文主要是介绍算法学习系列(四十一):Flood Fill算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 引言
  • 一、池塘计数
  • 二、城堡问题
  • 三、山峰和山谷

引言

关于这个 F l o o d F i l l Flood\ Fill Flood Fill 算法,其实我觉得就是一个 B F S BFS BFS 算法,模板其实都是非常相似的,只不过有些变形而已,然后又叫这个名字。关于 B F S BFS BFS 的知识可以参考我之前的博客: BFS博客链接 。因为就是一个 B F S BFS BFS 模型,所以该算法还是以讲题为主,那么接下来就开始吧。


一、池塘计数

标签:BFS、Flood Fill

思路:就是一个标准的 B F S BFS BFS 找连通块的数量,有区别的是这个连通块的标准是八连通的,这个只要在方向上再多设置几个就行了,其余的也没啥了。

题目描述:

农夫约翰有一片 N∗M 的矩形土地。最近,由于降雨的原因,部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内,如果包含雨水,则用”W”表示,如果不含雨水,则用”.”表示。现在,约翰想知道他的土地中形成了多少片池塘。每组相连的积水单元格集合可以看作是一片池塘。每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。请你输出共有多少片池塘,即矩阵中共有多少片相连的”W”块。输入格式
第一行包含两个整数 N 和 M。接下来 N 行,每行包含 M 个字符,字符为”W”或”.”,用以表示矩形土地的积水状况,字符之间没有空格。输出格式
输出一个整数,表示池塘数目。数据范围
1≤N,M≤1000
输入样例:
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出样例:
3

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1010;int n, m;
char g[N][N];
bool st[N][N];int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};void bfs(PII S)
{st[S.x][S.y] = true;queue<PII> q; q.push(S);while(q.size()){auto t = q.front(); q.pop();for(int i = 0; i < 8; ++i){int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= m) continue;if(st[x][y] || g[x][y] == '.') continue;st[x][y] = true;q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < n; ++i) cin >> g[i];int res = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(!st[i][j] && g[i][j] == 'W'){res++;bfs({i,j});}}}cout << res << endl;return 0;
}

二、城堡问题

标签:BFS

思路:这道题就是求连通块的数量和最大的连通块数,唯一的一个不同就是墙的定义变了,墙是拿一个数来表示的也就是如果为某个特定的数,那么该方向有墙。这个我们可以用位运算,来判定某一位是否为 1 1 1 ,然后把这个与方向对应就可以了,其余的就跟模板一样了。

题目描述:

    1   2   3   4   5   6   7  #############################1 #   |   #   |   #   |   |   ######---#####---#---#####---#2 #   #   |   #   #   #   #   ##---#####---#####---#####---#3 #   |   |   #   #   #   #   ##---#########---#####---#---#4 #   #   |   |   |   |   #   ##############################(图 1)#  = Wall   |  = No wall-  = No wall方向:上北下南左西右东。
图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成 m∗n个方格区域,每个方格区域可以有0~4面墙。注意:墙体厚度忽略不计。输入格式
第一行包含两个整数 m 和 n,分别表示城堡南北方向的长度和东西方向的长度。接下来 m 行,每行包含 n 个整数,每个整数都表示平面图对应位置的方块的墙的特征。每个方块中墙的特征由数字 P 来描述,我们用1表示西墙,2表示北墙,4表示东墙,8表示南墙,P 为该方块包含墙的数字之和。例如,如果一个方块的 P 为3,则 3 = 1 + 2,该方块包含西墙和北墙。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。输出格式
共两行,第一行输出房间总数,第二行输出最大房间的面积(方块数)。数据范围
1≤m,n≤50,0≤P≤15
输入样例:
4 7 
11 6 11 6 3 10 6 
7 9 6 13 5 15 5 
1 10 12 7 13 7 5 
13 11 10 8 10 12 13 
输出样例:
5
9

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 55;int n, m;
int g[N][N];
bool st[N][N];int dir[4][2] = {0,-1,-1,0,0,1,1,0};int bfs(PII S)
{st[S.x][S.y] = true;int cnt = 0;queue<PII> q; q.push(S);while(q.size()){auto t = q.front(); q.pop();cnt++;for(int i = 0; i < 4; ++i){if(g[t.x][t.y] >> i & 1) continue;  // 对应方向有墙int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= m) continue;if(st[x][y]) continue;st[x][y] = true;q.push({x,y}); }}return cnt;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){cin >> g[i][j];}}int res = 0, maxv = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(!st[i][j]){res++;maxv = max(maxv, bfs({i,j}));}}}cout << res << endl << maxv << endl;return 0;
}

三、山峰和山谷

标签:BFS

思路:就是枚举每一个连通块,然后判断周围是否有比它高,或者低的,如果没有那么就是山峰或者山谷,其余的就是模板。

题目描述:

FGD小朋友特别喜欢爬山,在爬山的时候他就在研究山峰和山谷。为了能够对旅程有一个安排,他想知道山峰和山谷的数量。给定一个地图,为FGD想要旅行的区域,地图被分为 n×n 的网格,每个格子 (i,j) 的高度 w(i,j) 是给定的。若两个格子有公共顶点,那么它们就是相邻的格子,如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),
(i+1,j),(i+1,j+1)。我们定义一个格子的集合 S 为山峰(山谷)当且仅当:S 的所有格子都有相同的高度。S 的所有格子都连通。
对于 s 属于 S,与 s 相邻的 s′ 不属于 S,都有 ws>ws′(山峰),或者 ws<ws′(山谷)。
如果周围不存在相邻区域,则同时将其视为山峰和山谷。
你的任务是,对于给定的地图,求出山峰和山谷的数量,如果所有格子都有相同的高度,那么整个地图即是山峰,又是山谷。输入格式
第一行包含一个正整数 n,表示地图的大小。接下来一个 n×n 的矩阵,表示地图上每个格子的高度 w。输出格式
共一行,包含两个整数,表示山峰和山谷的数量。数据范围
1≤n≤1000,0≤w≤109
输入样例1:
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
输出样例1:
2 1
输入样例2:
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7
输出样例2:
3 3

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1010;int n;
int h[N][N];
bool st[N][N];int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};void bfs(PII S, bool& has_high, bool& has_low)
{st[S.x][S.y] = true;queue<PII> q; q.push({S.x,S.y});while(q.size()){auto t = q.front(); q.pop();for(int i = 0; i < 8; ++i){int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= n) continue;if(h[x][y] > h[t.x][t.y]) has_high = true;if(h[x][y] < h[t.x][t.y]) has_low = true;if(st[x][y] || h[x][y] != h[t.x][t.y]) continue;st[x][y] = true;q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){cin >> h[i][j];}}int high = 0, low = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){if(!st[i][j]){bool has_high = false, has_low = false;bfs({i,j},has_high,has_low);if(!has_high) high++;if(!has_low) low++;}}}cout << high << " " << low << endl;return 0;
}

这篇关于算法学习系列(四十一):Flood Fill算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/826458

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用