当前位置: 首页 > news >正文

岛屿个数(dfs)

[第十四届蓝桥杯省B 岛屿个数]

小蓝得到了一副大小为 M × N M×N M×N 的格子地图,可以将其视作一个只包含字符 0 0 0(代表海水)和 1 1 1(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 1 1 1 相连接而形成。

在岛屿 A 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列: ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 ) (x_0,y_0),(x_1,y_1),...,(x_{k−1},y_{k−1}) (x0,y0),(x1,y1),...,(xk1,yk1),其中 (xi+1%k ,yi+1 % k) 是由
( x i , y i ) (x_i,y_i) (xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1),此时这 k 个格子就构成了一个 “环”。

如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部,此时我们将岛屿 B 视作是岛屿 A 的子岛屿。

若 B 是 A 的子岛屿,C 又是 B 的子岛屿,那 C 也是 A 的子岛屿。

请问这个地图上共有多少个岛屿?

在进行统计时不需要统计子岛屿的数目。

输入格式
第一行一个整数 T,表示有 T 组测试数据。

接下来输入 T 组数据。

对于每组数据,第一行包含两个用空格分隔的整数 M、N 表示地图大小;接下来输入 M 行,每行包含 N 个字符,字符只可能是 0 或 1。

输出格式
对于每组数据,输出一行,包含一个整数表示答案。

数据范围
对于 30% 的评测用例,1≤M,N≤10。
对于 100% 的评测用例,1≤T≤10,1≤M,N≤50。

输入样例:

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

输出样例:

1
3

样例解释
对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:

01111
11001
10201
10001
11111

岛屿 2 在岛屿 1 的 “环” 内部,所以岛屿 2 是岛屿 1 的子岛屿,答案为 1。

对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:

111111
100001
020301
100001
111111

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿,因为岛屿 1 和岛屿 2 中均没有“环”。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N=15;
typedef pair<int,int> PII; 
int a,b;
int g[N][N];
bool vis1[N][N],vis2[N][N];
//g陆地,vis1宽搜标记,vis2检查是否成环标记 void dfs(int x,int y){int dx[4]={1,0,-1,0};int dy[4]={0,1,0,-1};vis1[x][y]=true;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx<1||nx>a||ny<1||ny>b||vis1[nx][ny]||g[nx][ny]==0) continue;dfs(nx,ny);}
} bool check(int x,int y){int dx[8]={1,0,-1,0,1,1,-1,-1};int dy[8]={0,1,0,-1,1,-1,1,-1};for(int i=0;i<8;i++){int nx=x+dx[i],ny=y+dy[i];if(g[nx][ny]||vis2[nx][ny]) continue;if(nx<1||nx>a||ny<1||ny>b) return true;vis2[nx][ny]=1;if(check(nx,ny)) return true;}return false;
}int main () {int n;cin>>n;while(n--){memset(g,0,sizeof g);memset(vis1,0,sizeof vis1);memset(vis2,0,sizeof vis2);cin>>a>>b;for(int i=1;i<=a;i++)for(int j=1;j<=b;j++){char x;cin>>x;g[i][j]=x-'0';}int res=0;for(int i=1;i<=a;i++)for(int j=1;j<=b;j++){if(g[i][j]&&vis1[i][j]==0){vis1[i][j]=1;dfs(i,j);memset(vis2,0,sizeof vis2);vis2[i][j]=1;if(check(i,j)) res++;}}cout<<res<<endl;    }return 0;
}

相关文章:

岛屿个数(dfs)

[第十四届蓝桥杯省B 岛屿个数] 小蓝得到了一副大小为 M N MN MN 的格子地图&#xff0c;可以将其视作一个只包含字符 0 0 0&#xff08;代表海水&#xff09;和 1 1 1&#xff08;代表陆地&#xff09;的二维数组&#xff0c;地图之外可以视作全部是海水&#xff0c;每个岛…...

【C++造神计划】运算符

1 赋值运算符 赋值运算符的功能是将一个值赋给一个变量 int a 5; // 将整数 5 赋给变量 a 运算符左边的部分叫作 lvalue&#xff08;left value&#xff09;&#xff0c;右边的部分叫作 rvalue&#xff08;right value&#xff09; 左边 lvalue 必须是一个变量 右边 rval…...

Cortex-M3/M4处理器的bit-band(位带)技术

ARM Cortex-M3/M4的位带&#xff08;Bit-Band&#xff09;技术是一种内存映射技术&#xff0c;它允许对单个位进行直接操作&#xff0c;而不需要对整个字&#xff08;通常是32位&#xff09;进行操作。这项技术主要用于对特定的位进行高效的读写&#xff0c;特别是在需要对GPIO…...

【TOP】IEEE旗下1区,影响因子将破8,3个月录用,CCF推荐,性价比高!

计算机类 ● 好刊解读 IEEE出版社、中科院2区TOP&#xff0c;CCF推荐&#xff0c;今天推荐的期刊可谓buff叠满&#xff0c;好刊质量靠谱&#xff0c;有意向评职晋升毕业作者可重点关注&#xff1a; 01 期刊简介 ✅出版社&#xff1a;IEEE ✅影响因子&#xff1a;7.5-8.0 ✅…...

赚钱游戏 2.0.1 版 (资源免费)

没有c编辑器的可以直接获取资源来玩 #include <iostream> #include <string> #include <windows.h> #include <conio.h> #include <fstream> #include <ctime> #include <time.h> #include <stdio.h> #include <cstring&g…...

服务调用-微服务小白入门(4)

背景 各个服务应用&#xff0c;有很多restful api&#xff0c;不论是用哪种方式发布&#xff0c;部署&#xff0c;注册&#xff0c;发现&#xff0c;有很多场景需要各个微服务之间进行服务的调用&#xff0c;大多时候返回的json格式响应数据多&#xff0c;如果是前端直接调用倒…...

代码随想录算法训练营第三十六天| 435. 无重叠区间、 763.划分字母区间、56. 合并区间

435 题目&#xff1a; 给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。 题目链接&#xff1a;435. 无重叠区间 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; …...

【AIGC调研系列】rerank3是什么

Rerank 3是一个针对企业搜索和检索辅助生成&#xff08;RAG&#xff09;系统优化的新型基础模型&#xff0c;它支持多语种、多结构数据搜索&#xff0c;并提供高精度的语义重排。通过这种方式&#xff0c;Rerank 3能够大幅提升响应准确度和降低延迟&#xff0c;同时大幅降低成本…...

Linux下网络编程基础知识--协议

网络基础 这一个课程的笔记 相关文章 协议 Socket编程 高并发服务器实现 线程池 协议 一组规则, 数据传输和数据的解释的规则。 比如说依次发送文件的文件名, 文件的大小, 以及实际的文件, 这样规定发送一个文件的顺序以及发送的每一个部分的格式等可以算是一种协议 型协议 …...

在 VS Code 中使用 GitHub Copilot

Code 结合使用。 GitHub Copilot 是什么 GitHub Copilot 是一个可以帮助你更简单、更快速地编写代码的工具&#xff0c;由 GPT-3 提供支持。你只需编写所需代码的描述——例如&#xff0c;编写一个函数来生成一个随机数&#xff0c;或对一个数组进行排序——Copilot 就会为你…...

使用spring-ai快速对接ChatGpt

什么是spring-ai Spring AI 是一个与 Spring 生态系统紧密集成的项目&#xff0c;旨在简化在基于 Spring 的应用程序中使用人工智能&#xff08;AI&#xff09;技术的过程。 简化集成&#xff1a;Spring AI 为开发者提供了方便的工具和接口&#xff0c;使得在 Spring 应用中集…...

免费的 ChatGPT 网站(六个)

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《C》 《Linux》 《Cpolar》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 一、insCode二、讯飞星火三、豆包四、文心一言五、通义千问六、360智脑 现在智能…...

arm内核驱动-中断

先介绍个东西 ctags 这个工具可以像keil一样在工程里查找跳转&#xff0c;帮我们找到我们想要的东西。 安装教程可以找到&#xff0c;这里只讲怎么用。 在工程目录&#xff08;包含所有你会用到的头文件等&#xff09;下&#xff0c;先加载这个命令&#xff0c;可能要等待…...

第十五届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

试题 C: 好数 时间限制 : 1.0s 内存限制: 256.0MB 本题总分&#xff1a;10 分 【问题描述】 一个整数如果按从低位到高位的顺序&#xff0c;奇数位&#xff08;个位、百位、万位 &#xff09;上 的数字是奇数&#xff0c;偶数位&#xff08;十位、千位、十万位 &…...

kotlin编译版本

Kotlin和kapt的流行版本通常随着时间而变化&#xff0c;随着新版本的发布&#xff0c;更多的开发者会迁移到这些新版本。不过&#xff0c;由于Kotlin对向后兼容性的强调&#xff0c;大多数近期的Kotlin版本都支持Java 8。 截至本回答的知识截止日期&#xff08;2023年&#xff…...

【C#】 删除首/尾部字符

代码 static void Main(string[] args){string str "123abc";string strdelete "abc";string str1 str.Trim(1);string strc str1.Trim(c);string str11 str1.TrimStart(1);string strcc str1.TrimEnd(c);string strabc str.Trim(strdelete.ToCharA…...

第十五篇【传奇开心果系列】Python自动化办公库技术点案例示例:深度解读Python 自动化处理图像在各行各业的应用场景

传奇开心果博文系列 系列博文目录Python自动化办公库技术点案例示例系列 博文目录前言一、行业应用场景介绍二、 **计算机视觉研究与开发示例代码**三、人工智能与机器学习示例代码四、医疗健康领域示例代码五、制造业与质量控制示例代码六、农业与环境科学示例代码七、电子商务…...

什么是MOV视频格式?如何把MP4视频转MOV视频格式?

一&#xff0c;前言 当然可以&#xff0c;MP4视频可以转换为MOV格式。这两种格式都是常见的视频文件格式&#xff0c;它们都可以用于存储和播放视频内容。虽然它们的编码方式和特性有所不同&#xff0c;但使用合适的视频转换工具可以轻松地将MP4视频转换为MOV格式。 二&#…...

整理的微信小程序日历(单选/多选/筛选)

一、日历横向多选&#xff0c;支持单日、双日、三日、工作日等选择 效果图 wxml文件 <view class"calendar"><view class"section"><view class"title flex-box"><button bindtap"past">上一页</button&…...

Unity 人形骨骼动画模型嘴巴张开

最近搞Daz3D玩&#xff0c;导入后挂上动画模型嘴巴张开&#xff0c;其丑无比。 Google了一下&#xff0c;得知原因是Unity没有对下巴那根骨骼做控制&#xff0c;动画系统就会把它放到默认的位置&#xff0c;嘴巴就张开了。找到了3种解决办法。 1.移除动画中对下巴这个骨骼的转…...

Python爬虫-京东商品评论数据

前言 本文是该专栏的第68篇,后面会持续分享python爬虫干货知识,记得关注。 在本专栏之前,笔者有详细介绍京东滑块验证码的解决方法,感兴趣的同学,可以直接翻阅文章《Python如何解决“京东滑块验证码”(5)》进行查看。 而本文,笔者以京东商品详情页的评论数据为例,通过…...

实况窗助力美团打造鸿蒙原生外卖新体验,用户可实时掌握外卖进展

自2023年华为宣布全新HarmonyOS NEXT蓄势待发&#xff0c;鸿蒙原生应用全面启动以来&#xff0c;已有金融、旅行、社交等多个领域的企业和开发者陆续宣布加入鸿蒙生态。其中&#xff0c;美团作为国内头部的科技零售企业&#xff0c;是首批加入鸿蒙生态的伙伴&#xff0c;其下的…...

Go语言mac环境搭建详解

Go语言mac环境搭建详解见视频&#xff0c;视频下方也有讲解具体的操作步骤。 Golang Mac电脑环境搭建、开发工具Vscode配置 Go语言mac环境搭建步骤如下&#xff1a; 1、下载安装Golang Go官网下载地址&#xff1a;https://golang.org/dl/ Go官方镜像站&#xff08;推荐&…...

房贷还款(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h> # include <math.h>int main() {//初始化变量值&#xff1b;double m, r 0.01;float d 300000;float p 6000;//运算还款所需月份&#xff1b;m log10…...

系统架构最佳实践 -- 供应链系统架构

供应链系统是现代企业管理中不可或缺的一部分&#xff0c;它涉及到从原材料采购到产品销售的整个生产流程。一个高效的供应链系统可以帮助企业实现成本控制、库存优化和客户满意度提升等目标。在本文中&#xff0c;我们将讨论供应链系统的设计与实践。 一、供应链系统设计 业务…...

SpringCloudAlibaba-整合sentinel(四)

目录地址&#xff1a; SpringCloudAlibaba整合-CSDN博客 这里只关注代码部分&#xff0c;至于sentinel服务UI的实用&#xff0c;后面可以补上 这里做一个改造&#xff1a; 因为sentinel可以和openfeign结合使用&#xff0c;为微服务做熔断降级&#xff1b; 为了方便微服务之间…...

【研发日记】Matlab/Simulink软件优化(一)——动态内存负荷压缩

文章目录 背景介绍 初始代码 优化代码 分析和应用 总结 背景介绍 在一个嵌入式软件开发项目中&#xff0c;有一个使用MATLAB Function编写的算法模块&#xff0c;功能是从一个较大的数组中提取一段数据&#xff0c;然后求均值输出&#xff0c;示例如下&#xff1a; 初始代…...

python使用Flask框架开发API

Flask是一个基于Python的轻量级Web应用程序框架。 安装依赖库 pip install flask pip install werkzeug 上传接口 Python from flask import Flask, request from werkzeug.utils import secure_filenameapp Flask(__name__)app.route(/upload, methods[POST]) def uploa…...

使用hexo+gitee从零搭建个人博客

一、环境准备 1.Node.js&#xff1a;下载 | Node.js 中文网 (nodejs.cn) &#xff0c;Hexo 是基于Node.js 的博客框架 教程&#xff1a;https://blog.csdn.net/weixin_52799373/article/details/123840137 node -v npm -v 安装 Node.js 淘宝镜像加速器 &#xff08;cnpm&am…...

绝地求生:杜卡迪来了,这些摩托车技巧不学一下吗?

摩托车在远古版本和现在完全不一样&#xff0c;虽然容易翻车造就了一批玩家“摩托杀手”的外号&#xff0c;但是速度可比今天快多了。 后来在蓝洞的削弱了其加速度&#xff0c;虽然资料上写着最高时速155km/h&#xff0c;但是平时游戏中一般只能拉到110~120km/h。这里写一点摩托…...

怎么做网站界面分析/廊坊seo快速排名

一&#xff0c;介绍 本文介绍使用Kruskal算法求解无向图的最小生成树。Kruskal是一个贪心算法&#xff0c;并且使用了并查集这种数据结构。关于并查集的介绍&#xff0c;参考&#xff1a;数据结构--并查集的原理及实现 二&#xff0c;构造一个无向图 图&#xff0c;肯定有顶点和…...

怎么做阿里巴巴国际网站首页/广东今天新闻最新消息

2019独角兽企业重金招聘Python工程师标准>>> 今天在使用 codeigniter&#xff08;CI&#xff09;异步&#xff08;ajax&#xff09;传输数据时总是出现500 internal server error。 分两种分析&#xff0c;首先 如果使用url访问能够正确显示而没有这个错误&#xff…...

做生存曲线网站/深圳网络推广培训学校

非乐观锁场景时序图&#xff1a; 乐观锁场景示意图&#xff1a; 假设有一个账户余额表 user_balance&#xff0c;其中有两个字段&#xff1a;user_id 和 balance&#xff0c;分别表示用户 ID 和账户余额。现在有两个用户同时进行充值操作&#xff0c;充值金额分别为 100 元…...

b2c网站建设平台/最新疫情最新数据

目录 DCOM 本地DCOM执行命令 获取DCOM程序列表 使用DCOM执行任意系统命令...

国外平面设计/优化网站做什么的

BCD码一般在时钟芯片中会采用&#xff0c;比如2019-03-29 15:42:54会表示为 0x20 0x19 0x03 0x29 0x15 0x42 0x54&#xff0c;具体十进制跟BCD码的关系可以百度&#xff1b;BCD转为十进制 int BCDToInt(unsigned char value) {int temp 0;temp (value>>4)*10;temp va…...

网站用哪些系统做的好处/站长统计app下载免费

当下物联网发展迅猛&#xff0c;物联网卡可以接受短信指令&#xff0c;实现千里之外尽可掌控。本人做过一个这类项目&#xff0c;把相关经验记录下来&#xff0c;分享给需要的人。 物联网卡通讯其实跟电话卡一样&#xff0c;可以使用CMPP协议。不过由于物联网卡位数为13位&…...