【洛谷】P1596Lake Counting S(BFS解决连通性问题模板)

 

杂谈 

大部分与检验连通性有关的题目,都可以归结为一个迷宫问题,那么就是 bfs 问题,可以查看一下笔者最近几篇用搜索方法解决连通性问题的题解,其中 bfs 解决的步骤十分固定,甚至可以说几道题的代码几乎一样,比如下面这道:

【洛谷】P1162填涂颜色(BFS)-CSDN博客

如果对迷宫模型感兴趣,可见下面这两道: 

【洛谷】P1443 马的遍历(BFS)-CSDN博客

走迷宫(BFS + 队列)-CSDN博客

连通性问题的解决思路

(1) 遍历整张地图中的某些点(这道题遍历了整张地图,P1162填涂颜色遍历了地图的四条边,具体遍历哪些点根据具体情况确定,嫌麻烦的话直接遍历整张地图也无所谓,不会带来太大开销),从特定点开始 bfs 。这道题中要找水坑数量,因此从有水的地方开始 bfs;

(2)定义特定的数据结构。笔者习惯定义一个结构体 point 以及一个队列,一般来说队列是必需的,point 可以换成其它方便解题的数据结构,如 pair 或其它;

(3)编写 bfs 函数。在这道题以及上面提到过的两种迷宫模型中,笔者已经将 bfs 函数模板化了,这四篇题解中的 bfs 函数可以说长得一样,引用走迷宫这道题中对 bfs 步骤的总结:

#include<iostream>
#include<queue> 
using namespace std;

struct point{
	int x;
	int y;
	point(int a, int b)
	{
		x = a;
		y = b;
	}
};

queue<point> q;
int n,m,res;
char map[105][105] = {0};
int dx[8] = {0,1,1,1,0,-1,-1,-1};
int dy[8] = {1,1,0,-1,-1,-1,0,1};

void bfs(int x, int y)
{
    // 初始化队首
	q.push(point(x,y));
	map[x][y] = '.';
	
    // 队列非空时说明还能往下走,则继续循环,否则退出循环
	while(!q.empty())
	{
		for(int i=0;i<8;++i)
		{
			int a = q.front().x + dx[i];
			int b = q.front().y + dy[i];
			if(map[a][b] == 'W' && a >= 0 && a <= n && b >= 0 && b <= m)
			{
				q.push(point(a,b)); // (a,b)是可以走到的点,放入队列
				map[a][b] = '.';    // 将走过的点标记为旱地,防止重走一遍
			}
		}
		q.pop();
	}
    // 结束一次while循环说明找完了一整个水池,因此增加水池的数量
	++res;
}

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			cin>>map[i][j];
	
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			if(map[i][j] == 'W')
				bfs(i,j); 
				
	cout<<res;
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Leetcode刷题笔记题解(C++):257. 二叉树的所有路径

思路&#xff1a;深度优先搜索 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right…

posix_memalign 与 malloc 对比

1. 原因原理 编程中的类型对齐问题主要是处于性能考虑&#xff0c;如果不做对齐&#xff0c;那么单个数据元素的访问很容易跨在多个时钟周期上&#xff0c;从而导致性能下降。 内建数据类型的对齐&#xff0c;是由编译器和C语言库的API实现中自动完成的&#xff0c;这对于用户是…

红队打靶练习:HEALTHCARE: 1

目录 信息收集 1、arp 2、nmap 3、nikto 4、whatweb 目录探测 1、gobuster 2、dirsearch WEB web信息收集 gobuster cms sqlmap 爆库 爆表 爆列 爆字段 FTP 提权 信息收集 本地提权 信息收集 1、arp ┌──(root㉿ru)-[~/kali] └─# arp-scan -l Inte…

Vision Transformer(二):位置嵌入向量

1. 什么是位置嵌入向量 位置嵌入向量是Transformer兴起时就引入的一个概念。早期在处理文本信息时&#xff0c;词语之间是相关联的&#xff0c;只有具有一定位置关系的词语组合才能够表达一些正确的意思。 2. 在Transformer中是如何实现的&#xff1f; 在Transformer的训练过…

ubuntu22.04@laptop OpenCV Get Started: 000_hello_opencv

ubuntu22.04laptop OpenCV Get Started: 000_hello_opencv 1. 源由2. Hello OpenCV2.1 C应用Demo2.2 Python应用Demo 3. 参考资料 1. 源由 之前&#xff0c;通过敲门砖已经砸开了OpenCV的大门&#xff0c;接下来是体验下“Hello World&#xff01;”程序。 2. Hello OpenCV …

洗地机值得买吗?四款好用的洗地机推荐

洗地机值得买吗&#xff0c;相比传统清洁工具而言&#xff0c;洗地机的优势明显&#xff0c;甚至可以说是代差级的优势。它可以一机多用&#xff0c;在扫地、拖地、滚刷自清洁、烘干/晾干上一次完成&#xff0c;不仅清洁能力强大又大大减少了家务所需的时间&#xff0c;是正儿八…

啤酒:畅享精酿啤酒与海鲜的鲜美滋味

夏日的阳光总是让人心生慵懒&#xff0c;而在这个季节里&#xff0c;没有什么比一杯冰镇啤酒和一串烤肉更能令人感到惬意了。当Fendi Club啤酒与烤肉相遇&#xff0c;它们将为你的夏日时光增添无尽的欢愉。 Fendi Club啤酒&#xff0c;以其醇厚的口感和酿造工艺收获了许多的啤酒…

専攻春节钜惠

専攻春节钜惠 大家好&#xff0c;新春佳节到来之际&#xff0c;为了答谢大家多年来的支持厚爱&#xff0c;也为了更广泛的推广VBA应用&#xff0c;“VBA语言専攻”在春节期间再次推出钜惠活动&#xff0c;时间2月9日到2月17日&#xff08;大年三十到正月初八&#xff09; 1 &…

宠物空气净化器哪个品牌质量好?实惠的猫用猫用净化器牌子测评

作为宠物主人&#xff0c;我们深知养宠物的乐趣和责任&#xff0c;但同时也面临着一些挑战&#xff0c;比如宠物脱毛、气味和室内空气质量等问题。正因如此&#xff0c;越来越多的家庭选择宠物空气净化器&#xff0c;为我们营造一个清新、健康的居住环境。 无论我们多么喜欢我…

Dijkstra算法(求最短路)

简介&#xff1a; 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的&#xff0c;因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法&#xff0c;解决的是有权图中最短路径问题。 特点&#xff1a; 迪杰斯特拉算法采用的是一种贪心策略&a…

双侧条形图绘制教程

写在前面 双侧条形图在我们的文章中也是比较常见的&#xff0c;那么这样的图形是如何绘制的呢&#xff1f; 以及它使用的数据类型是什么呢&#xff1f; 这些都是我们在绘制图形前需要掌握的&#xff0c;至少我们知道绘图的数据集如何准备&#xff0c;这样才踏出第一步。 今天…

代码审计-CVE-2023-6654-PHPEMS-加密-解密分析

路由&#xff1a; 入口方法&#xff1a; 鉴权分析&#xff1a; 由此可以得出 鉴权是由session类负责获取参数后&#xff0c;由各个类的魔术方法负责&#xff1a;&#xff08;在此还有一个方法 全局搜索登录关键词&#xff09; 1、断点分析&#xff1a; 寻找鉴权点分析&#…

ref用法

目录 React中提供两种方法创建ref对象&#xff1a; 类组件获取 Ref 三种方式 ① Ref属性是一个字符串。 ② Ref 属性是一个函数。 ③ Ref属性是一个ref对象。 高级用法1&#xff1a;forwardRef 转发 Ref 高级用法2&#xff1a;ref实现组件通信 【ref作用】&#xff1a;最…

UE4 C++创建摄像机摇臂和相机并且设置Transform

新建MyPawn C类 .h #include "GameFramework/SpringArmComponent.h" //SpringArm组件 #include "Camera/CameraComponent.h" //Camera组件class 工程名称_API AMyPawn : public APawn { //定义组件变量 public:UPROPERTY(VisibleAnywhere, BlueprintRead…

CSS:两列布局

两列布局是指一列宽度固定&#xff0c;另一列自适应。效果如下&#xff1a; HTML: <div class"container clearfix"><div class"left"></div><div class"right"></div> </div>公共 CSS&#xff1a; .con…

2024年2月CCF-全国精英算法大赛题目

第一次参加这种比赛&#xff0c;虽然是c类赛事&#xff0c;但是是ccf主办的&#xff0c;难度还是有点的&#xff0c;主要是前面签到题主要是思想&#xff0c;后面的题目难度太高&#xff0c;身为力扣只刷了一百多道题目的我解决不了&#xff0c;这几道我只做了B,C题,E题超时了&…

HR看了都想点开的简历:吸睛模板+撰写技巧

工作致富的第一步&#xff1a;写一份好的简历。一个独特、简单、清晰的个人简历模板可以更好地吸引雇主的注意和兴趣&#xff0c;并帮助你在许多求职者中脱颖而出。如何制作一份令人印象深刻的简历&#xff1f;巧妙地使用个人简历模板是一个不错的选择。在本文中&#xff0c;我…

Spring Boot整合新版Spring Security:Lambda表达式配置优雅安全

文章目录 1. 引言2. 项目依赖配置3. 使用Lambda表达式配置Spring Security4. 自定义身份验证逻辑5. 认证与授权注解5.1 Secured注解5.2 PreAuthorize和PostAuthorize注解 6. 总结 &#x1f389;Spring Boot整合新版Spring Security&#xff1a;Lambda表达式配置优雅安全 ☆* o(…

STM32F1 - 点灯-寄存器模式

点灯 实验概述&#xff1a;Step1> 建立工程Step2> 宏定义 - 寄存器地址 实验概述&#xff1a; 用配置寄存器的方式&#xff0c;开关一个LED灯&#xff0c; 只用标准库中提供的启动文件&#xff0c; Step1> 建立工程 出现错误&#xff1a;导入文件类型错误 keil5编译中…

QT Linux下无法使用CTRL+ALT+P快捷键,不生效

文章目录 一、背景二、排查&#xff08;1&#xff09;检查创建&#xff0c;发现没问题。&#xff08;2&#xff09;查看 shortcutMap 是否注册&#xff08;3&#xff09;排查xcb有没有获取到该事件&#xff08;4&#xff09;排查是否是系统的问题&#xff08;5&#xff09;www.…