蓝桥杯-岛屿个数

news/2024/6/20 21:00:30/文章来源:https://blog.csdn.net/Moliay/article/details/137139188

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

solution

数1的块数题,加了内岛不计入的小限制,以及输入数据间没有空格,不是矩阵形式的整数输入。

  • 判断是否是子岛屿:如果该岛屿有边缘部分或者可以通过外海走到边缘部分说明不是子岛屿
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn = 55;
int t, n, m, a[maxn][maxn], flag[maxn][maxn], vis[maxn][maxn], ans;
string s;
struct Node{int x, y;
}node, node1;
int X[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
int Y[8] = {0, 0, -1, 1, 1, -1, -1, 1};void bfs(int x, int y){queue<Node> q;node.x = x;node.y = y;flag[x][y] = 1;q.push(node);while(!q.empty()){Node top = q.front();q.pop();for(int i = 0; i < 4; i++){int newx = top.x + X[i];int newy = top.y + Y[i];if(newx < 0 || newx >= m || newy < 0 || newy >= n) continue;if(flag[newx][newy] || !a[newx][newy]) continue;node1.x = newx;node1.y = newy;flag[newx][newy] = 1;q.push(node1);}}
}bool judge(int x, int y){for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){vis[i][j] = 0;}}queue<Node> q;node.x = x;node.y = y;vis[x][y] = 1;q.push(node);while(!q.empty()){Node top = q.front();q.pop();if(top.x == 0 || top.x == m - 1 || top.y == 0 || top.y == n - 1) return true;//能走到边缘就证明没有在环内for(int i = 0; i < 8; i++){int newx = top.x + X[i];int newy = top.y + Y[i];if(vis[newx][newy] || a[newx][newy]) continue;if(x < 0 || x >= m || y < 0 || y >= n) continue;node1.x = newx;node1.y = newy;q.push(node1);vis[newx][newy] = 1;}}return false;
}int main(){scanf("%d", &t);while(t--){scanf("%d%d", &m, &n);ans = 0;for(int i = 0; i < m; i++){cin >> s;for(int j = 0; j < n; j++){a[i][j] = s[j] - '0';flag[i][j] = 0;}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!flag[i][j] && a[i][j]){bfs(i, j);if(judge(i, j)) ans ++;}}}printf("%d\n", ans);}	return 0;
}

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

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

相关文章

Django创建多app应用

目录 1. 引言 2. 多app创建的两种方式 2.1 多个app结构 2.2 单个apps多个app 3. 最后 1. 引言 在平常业务开发中&#xff0c;我们遇到的功能可能会有很多&#xff0c;单个app的应用可能无法满足我们 这个时候&#xff0c;我们就需要多app应用&#xff0c;例如&#xff1a…

基于SSM+Jsp+Mysql的固定资产管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

在线考试系统的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码+数据库+设计文档)

本项目包含可运行源码数据库LW&#xff0c;文末可获取本项目的所有资料。 推荐阅读300套最新项目持续更新中..... 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 2024年56套包含ja…

Linux 系统 安装redis

Linux 系统 安装redis 下载redis安装包&#xff0c;并上传到服务器指定安装目录 一、解压安装包并安装 1、 tar xzf redis-4.0.9.tar.gz 2、先通过gcc -v是否有安装gcc&#xff0c;如果没有安装 统一安装Gcc rpm -Uvh *.rpm --nodeps --force 3、cd /usr/local/red…

前端之HTML——网页的骨架!!

目录 一、HTML介绍 二、HTML标签 &#xff08;一&#xff09;基础标签 &#xff08;二&#xff09;其他标签 2.1 6个常用标签 2.2 8个文本标签 2.3 6个列表标签 2.4 4个表格标签 2.5 4个媒体标签 2.6 1个嵌入标签 2.7 …

HBuilder uniapp发行h5遇到报错:此应用 DCloud appid 为 __UNI__95950AD ,您不是这个应用的项目成员。

uniapp打包遇到不是项目成员问题&#xff0c;如下截图&#xff1a; 解决方法如下&#xff1a; 打开项目的mainfest.json文件&#xff0c;在AppID位置点击重新获取&#xff0c;获取后重新点发行打包即可 另遇到HBuilder账号认证问题&#xff0c;如公司wifi打不开认证地址&#…

一文入门Ubuntu22

目录 1.安装Ubuntu22 2.常用目录 3.常用指令 1.sudo 超级用户权限运行命令 2.ls 罗列当前文件信息 3.文件目录相关&#xff1a; 1.cd改变工作路径&#xff1a; 2.pwd 3.创建目录和文件&#xff1a; 4.which 5.ps 6.kill 7.ping 4.用户相关 5.ssh与scp 6.服务相关…

【氮化镓】GaN器件中关态应力诱导的损伤定位

概括总结&#xff1a; 这项研究通过低频1/f噪声测量方法&#xff0c;探究了在关态&#xff08;OFF-state&#xff09;应力作用下&#xff0c;AlGaN/GaN高电子迁移率晶体管&#xff08;HEMTs&#xff09;中由应力引起的损伤的定位。研究中结合了电致发光&#xff08;EL&#xf…

谈谈MVCC机制

在MySQL中&#xff0c;MVCC&#xff08;多版本并发控制&#xff09;是InnoDB存储引擎使用的并发控制机制。它提供对数据的并发访问&#xff0c;并确保多用户环境中数据的一致性和隔离性。 InnoDB通过“Undo log”存储每条记录的多个版本&#xff0c;提供历史记录供读取&#x…

Spring Boot项目启动速度优化

1、配置自动配置排除列表&#xff0c;减少启动自动配置扫描&#xff0c;配置项spring.autoconfigure.exclude 2、启动类添加索引注解Indexed&#xff0c;去除启动过程中 Components 的扫描步骤&#xff0c;直接从索引文件读取。 import org.springframework.stereotype.lndexe…

自定义 Unity Scene 的界面工具

介绍 文档中会进行SceneView的自定义扩展&#xff0c;实现显示常驻GUI和添加自定义叠加层&#xff08;Custom Overlay&#xff09;。 最近项目开发用回了原生的Unity UI相关内容。对于之前常用的FairyGUI来说&#xff0c;原生的UGUI对于UI同学来讲有些不太方便。再加上这次会…

【精品方案】智慧金融大数据分析平台总体架构方案

以下是部分PPT内容&#xff0c;请您参阅。如需下载完整PPTX文件&#xff0c;请前往星球获取&#xff1a; 1.实现数据共享 通过数据平台实现数据集中&#xff0c;确保金融集团各级部门均可在保证数据隐私和安全的前提下使用数据&#xff0c;充分发挥数据作为企业重要资产的业务价…

String Encryptor custom Bean not found with name ‘jasyptStringEncryptor‘...

项目采用 spring boot 2.6.13 jasypt-spring-boot-starter 3.0.5 apollo-client 1.6.0 自定义jasyptStringEncryptor&#xff0c;服务器上启动死活报找不到bean jasyptStringEncryptor&#xff0c;采用默认的&#xff0c;密文配置项自然解密失败导致服务无法启动。 经过一…

华为云RDS for Mysql入门与配置

华为云RDS for MySQL支持混合SSD实例&#xff0c;它结合了华为云容器、本地SSD盘和高速云盘。 优势&#xff1a; 主备实例提供故障自动切换和手动切换&#xff0c;业务中断时间为秒级&#xff0c;以及异地灾难备份&#xff0c;最大程度上在出现故障的情况下保障整个数据库集群…

基于STM32的汽车防窒息系统

文章目录 基于STM32的汽车防窒息系统系统简介材料展示视频制作硬件连接原理图PCB实物图GSM模块使用GSM模块代码 SGP30模块SGP30模块代码 步进电机驱动步进电机代码 其他模块主逻辑代码 总结 基于STM32的汽车防窒息系统 系统简介 随着社会的发展目前汽车的流行&#xff0c;汽车大…

WebSocket 和 HTTP 的区别:简单易懂

在当今的数字时代&#xff0c;及时交付内容和维持用户互动已成为网络应用不可或缺的要素。这一需求催生了新的通信规范——WebSocket 和 HTTP&#xff0c;尽管两者都服务于网络通讯&#xff0c;它们之间却存在显着的差异。本篇文章旨在剖析这两种协议在应用案例、技术细节、性能…

C语言动态内存讲解+通讯录2.0

文章目录 前文malloc和freecallocrealloc枚举常量的简单说明及使用 通讯录2.0动态开辟通讯录,满了就扩容保存数据和载入数据 通讯录2.0演示推荐好用的软件 前文 本文主要介绍动态开辟的几个函数,以及改进之前的通讯录。 我们局部变量等是在栈区上开辟空间的,而我们动态开辟的空…

微信小程序开发【从入门到精通】——页面导航

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

绘制特征曲线-ROC(Machine Learning 研习十七)

接收者操作特征曲线&#xff08;ROC&#xff09;是二元分类器的另一个常用工具。它与精确度/召回率曲线非常相似&#xff0c;但 ROC 曲线不是绘制精确度与召回率的关系曲线&#xff0c;而是绘制真阳性率&#xff08;召回率的另一个名称&#xff09;与假阳性率&#xff08;FPR&a…

42.网络游戏逆向分析与漏洞攻防-角色管理功能通信分析-角色删除功能的封装

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 如果看不懂、不知道现在做的什么&#xff0c;那就跟着做完看效果 内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;41.角色删除功能…