洛谷 池塘计数 floor-fill BFS 模板题

news/2024/4/19 0:12:04

🍑 OJ专栏


🍑 P1596 Lake Counting

题面翻译

由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个 N × M ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ 100 ) N\times M(1\leq N\leq 100, 1\leq M\leq 100) N×M(1N100,1M100) 的网格图表示。每个网格中有水(W) 或是旱地(.)。一个网格与其周围的八个网格相连,而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图,确定当中有多少水坑。

输入第 1 1 1 行:两个空格隔开的整数: N N N M M M

2 2 2 行到第 N + 1 N+1 N+1 行:每行 M M M 个字符,每个字符是 W.,它们表示网格图中的一排。字符之间没有空格。

输出一行,表示水坑的数量。

题目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

输入格式

Line 1: Two space-separated integers: N and M * Lines 2…N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

输出格式

Line 1: The number of ponds in Farmer John’s field.

样例 #1

样例输入 #1

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出 #1

3

提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.


🍑 模板题

import java.util.*;class Main{static int N = 110,n,m;static char[][] g = new char[N][N];static boolean[][] st = new boolean[N][N];static Node[] q = new Node[N*N];// 队列最多有N*N个点// 点类static class Node{int x;int y;public Node(int x,int y){this.x = x;this.y = y;}}// sx,sy 是起点的坐标static void bfs(int sx,int sy){st[sx][sy] = true;//标记地点q[0] = new Node(sx,sy);int hh = 0;int tt = 0;while(hh <= tt){Node t = q[hh++];//队首出列int x = t.x;int y = t.y;for(int xx = x-1; xx <= x+1; xx++)for(int yy = y-1; yy <= y +1; yy++){if(xx >= n || xx < 0 || yy >= m || yy < 0)continue;//{xx,yy} == {x,y} 的情况已经遍历过了,无需特殊处理if(st[xx][yy]  || g[xx][yy] == '.')continue;st[xx][yy] = true;q[++tt] = new Node(xx,yy);//从队尾入列}}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();sc.nextLine();for(int i = 0; i < n; i++){String s = sc.nextLine();for(int j = 0; j < m; j++)g[i][j] = s.charAt(j);}   int cnt = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(!st[i][j] && g[i][j] == 'W'){bfs(i,j);//找到一块池塘,就把它所在的连通块去掉cnt++;}System.out.println(cnt);}}

http://www.ppmy.cn/news/73365.html

相关文章

Qt——Qt控件之显示窗口-QLabel标签控件的使用总结(例程:QLabel显示文本标签及图片)

【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》

【CSS 选择器应用在QSS】第二天

CSS 选择器应用在QSS 【1】元素选择器&#xff08;元素通用性&#xff09;【2】id 选择器&#xff08;唯一性&#xff09;【2.1】CSS【2.2】QSS 【3】类选择器【3.1】CSS【3.2】QSS 【4】类选择器&#xff08;只针对指定元素&#xff09;【4.1】CSS【4.2】QSS 【5】通用选择器【…

语音合成工具_bark

1 介绍 多语言的文字转语音模型。 地址: https://github.com/suno-ai/bark 2 模型原理 Bark通过三个Transformer模型&#xff0c;将文本转换为音频。 2.1 文本到语义Token 输入&#xff1a;由Hugging Face的BERT标记器分词的文本 输出&#xff1a;编码生成音频的语义Token…

【面试高频 time: 2023-5-18】做分布式文件存储,如何保证分布式存储的高性能与高可用?

大家可以想到基本就是副本备份、双活、多活这种架构 在系统中通过复制协议将数据同步到多个存储节点&#xff0c;并确 保多个副本之间的数据⼀致性&#xff0c;当某个存储节点出故障 时&#xff0c;系统能够⾃动将服务切换到其他的副本 在分布式存储中⾼性能与⾼可⽤是⽭盾的&…

手把手教你怎么搭建自己的ChatGPT和Midjourney绘图(含源码)

AI程序采用NUXT3LARAVEL9开发&#xff08;目前版本V1.1.7&#xff09; 授权方式&#xff1a;三个顶级域名两次更换 1.AI智能对话-对接官方和官方反代&#xff08;markdown输出&#xff09;PS:采用百度与自用库检测文字 2.AI绘图-根据关键词绘图-增加dreamStudio绘画-增加mid…

Requests的使用例子

Requests库是一个Python HTTP客户端库&#xff0c;用于向Web服务器发送HTTP请求。它提供了简单而直观的API&#xff0c;使得向Web服务器发送HTTP请求变得非常容易。以下是Requests库的一些功能和示例&#xff1a; 1、发送HTTP GET请求 发送HTTP GET请求非常简单&#xff0c;只…

查看linux日志以及处理不能登录mysql的错误

要查看MariaDB的日志文件&#xff0c;可以使用以下命令&#xff1a; 1. 错误日志文件&#xff1a; bash sudo cat /var/log/mariadb/error.log 这将显示MariaDB的错误日志文件的内容。如果在默认位置找不到错误日志文件&#xff0c;您可以尝试查找其他可能的位置&#…

Activiti实战——Springboot整合Activiti

目录 一、Activiti数据库表名说明 二、Spring boot整合activiti 1. 创建springboot项目 2. 引入activiti依赖及项目依赖 3. 配置数据源 &#xff08;1&#xff09;创建数据源配置文件 &#xff08;2&#xff09;配置文件 4. 配置Acitviti引擎 5. 启动项目 三、Activiti…

DJ5-4 交换局域网(第一节课)

目录 一、局域网概述 1、LAN 的特点和分类 2、常见的网络拓扑结构 二、计算机与局域网的连接 三、局域网体系结构 四、链路层寻址地址 1、MAC 地址分配 2、MAC 地址识别 五、ARP 地址解析协议 1、ARP 地址解析协议 2、ARP&#xff1a;两个主机位于同一个局域网 3、…

Godot引擎 4.0 文档 - 入门介绍 - Godot 关键概念概述¶

本文为Google Translate英译中结果&#xff0c;DrGraph在此基础上加了一些校正。英文原版页面&#xff1a;Overview of Godots key concepts — Godot Engine (stable) documentation in English Godot 关键概念概述 每个游戏引擎都围绕您用来构建应用程序的抽象展开。在 Godo…

AUTOSAR知识点 之 COM (二):ISOLAR-AB的配置

目录 1、概述 2、ISOLAR-AB配置 2.1、ComGeneral 2.2、ComConfig 2.2.1、ComGwMapping 2.2.2、ComIPduGroups 2.2.3、ComIPdus

超越大数据的边界:Apache Flink实战解析【上进小菜猪大数据系列】

上进小菜猪&#xff0c;沈工大软件工程专业&#xff0c;爱好敲代码&#xff0c;持续输出干货。欢迎订阅专栏 Apache Flink是一种快速、可靠、可扩展的开源流处理框架&#xff0c;被广泛应用于大数据领域。本文将介绍Apache Flink的实战运用&#xff0c;包括其核心概念、架构设…

LeetCode346场周赛

2023.5.21LeetCode346场周赛 A. 删除子串后的字符串最小长度 思路 使用栈模拟&#xff0c;每当遇到AB和CD时出栈 代码 class Solution { public:int minLength(string s) {string res s.substr(0, 1);for (int i 1; i < s.size(); i ) {res s[i];int n res.size()…

选择性搜索算法(Selective Search )——SS算法

文章目录 一、前言二、object Detection VS object Recognition&#xff08;Selective Search的提出&#xff09;2.1object recognition与object detection的关系2.2滑动窗口方法的局限性2.3Selective search算法的提出 三、Selective Search算法3.1什么是Selective Search&…

基于yolov3训练自己的数据集

训练数据集的教学视频链接 42. 第六章&#xff1a;基于YOLO-V3训练自己的数据集与任务_哔哩哔哩_bilibili 数据打标签 下载labelme标注工具 通过pip install labelme下载&#xff0c;打开anaconda prompt&#xff0c;切换到下载labelme的环境&#xff08;我的是pytorch&…

异步线程:CompletableFuture、@Async

区别: 1.CompletableFuture是java中提供的一个异步执行类&#xff0c;Async是Spring提供的异步执行方法&#xff0c;当调用方法单独开启一个线程进行调用。 2.Async通常指定一个方法使用的异步方法调用&#xff0c;而CompletableFuture可以一个方法体内对请求体进行排序组合成…

yolov5剪枝与知识蒸馏【附代码】

剪枝和知识蒸馏均属于模型轻量化设计&#xff0c;剪枝是将已有网络通过剪枝的手段得到轻量化网络&#xff0c;可分为非结构化剪枝和结构化剪&#xff0c;该技术可以免去人为设计轻量网络&#xff0c;而是通过计算各个权重或者通道的贡献度大小&#xff0c;剪去贡献度小的权重或…

面了个 Java 实习生,小伙很优秀!

大家好&#xff0c;我是鱼皮&#xff0c;前几天给自己的公司面试了一位 Java 暑期实习生&#xff0c;候选人目前是大三。 整个过程我都录屏了&#xff0c;并且在征得候选人的同意后&#xff0c;把面试过程分享出来。一方面是希望对其他在学编程找工作的小伙伴有一些启发和参考…

思迈特软件Smartbi荣登“2023未来银行科技服务商100强”

近日&#xff0c;中国科学院《互联网周刊》、eNet研究院联合发布了“2023未来银行科技服务商100强”企业榜单。思迈特软件以“商业智能BI产品”凭借在金融科技创新的独特优势及在银行数字化转型实践中的卓越成就荣耀上榜。 据了解&#xff0c;“未来银行科技服务商100强”榜单&…

Spring IOC 的理解

IoC容器是什么&#xff1f; IoC文英全称Inversion of Control&#xff0c;即控制反转&#xff0c;我么可以这么理解IoC容器&#xff1a; “把某些业务对象的的控制权交给一个平台或者框架来同一管理&#xff0c;这个同一管理的平台可以称为IoC 容器。” 我们刚开始学习…