DS图—图非0面积/bfs【数据结构】
DS图—图非0面积
题目描述
编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示,在10*10的二维数组中,"1"围住了15个点,因此面积为15。
提示:queue
输入
测试次数t
每组测试数据格式为:
数组大小m,n
一个由0和1组成的m*n的二维数组
输出
对每个二维数组,输出符号"1"围住的"0"的个数,即围成的面积。假设一定有1组成的闭合曲线,但不唯一。
输入样例1
2
10 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
5 8
0 1 1 0 0 1 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0
0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0
输出样例1
15
5
bfs
思路:根据题意,只有完全被1围起来的0才算,所以四个边的0都是不行的,而且其他0一旦bfs的时候碰到了四条边上的0也是不行的。遍历0并且用bfs找0
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int b[4]={0,1,0,-1};
int c[4]={1,0,-1,0};
int bfs(int a[][105],int visited[][105],int x,int y,int m,int n)
{queue<P> q;q.push({x,y});visited[x][y]=1;int num=0;while(!q.empty()){P k=q.front();q.pop();num++;x=k.first;y=k.second;for(int i=0;i<4;i++){int xx=x+b[i];int yy=y+c[i];if(a[xx][yy]==0&&!visited[xx][yy]){//碰到边肯定不行if(xx==0||xx==m-1||yy==0||yy==n-1) return -1;q.push({xx,yy});visited[xx][yy]=1;}}}return num;
}
int main()
{int t;cin>>t;for(int i=0;i<t;i++){int m,n;cin>>m>>n;int a[105][105];for(int j=0;j<m;j++){for(int k=0;k<n;k++) cin>>a[j][k];}int res=0;//记录已经被算上的0 不用重复遍历它们int allvisited[105][105]={0};for(int j=1;j<m-1;j++){for(int k=1;k<n-1;k++){//记录一次bfs的访问记录,如果这个bfs最后返回-1,则访问记录不用同步到allvisited上,否则要int visited[105][105]={0};int b;if(a[j][k]==0&&allvisited[j][k]==0&&(b=bfs(a,visited,j,k,m,n))!=-1){int w=b;res+=w;//将一次bfs访问的0同步到allvisited上for(int q=0;q<m;q++){for(int r=0;r<n;r++){if(visited[q][r]==1) allvisited[q][r]=1;}}}}}cout<<res<<endl;}return 0;
}
相关文章:
DS图—图非0面积/bfs【数据结构】
DS图—图非0面积 题目描述 编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示,在10*10的二维数组中,"1"围住了15个点,因此面积为15。 提示&…...
Wnmp服务安装并结合内网穿透实现公网远程访问——“cpolar内网穿透”
文章目录 前言1.Wnmp下载安装2.Wnmp设置3.安装cpolar内网穿透3.1 注册账号3.2 下载cpolar客户端3.3 登录cpolar web ui管理界面3.4 创建公网地址 4.固定公网地址访问 前言 WNMP是Windows系统下的绿色NginxMysqlPHP环境集成套件包,安装完成后即可得到一个Nginx MyS…...
2023版Pycharm关闭一直显示closing project,正在关闭项目
点击 帮助 下的 查找操作 英文版为 Help 下的 Find Action 输入 Registry 禁用 ide.await.scope.completion 即可 PS:按 Ctrl F 输入可以快速检索...
Gradle笔记 二 Gradle的基础Groovy
学习Groovy的必要性 首先Gradle是由Groovy写成的,而且构建脚本的语法都遵循Groovy的语法,所以要学好Gradle的前提是要基本了解Groovy的语法。 Groovy 简介 在某种程度上,Groovy可以被视为Java的一种脚本化改良版,Groovy也是运行在JVM上&am…...
浅谈剩余电流动作继电器在电动伸缩门的应用
摘 要:随着时代的发展,越来越多的小区、厂区、园区和学校等场所的大门安装了电动伸缩门,几乎可以说随处可见。电动伸缩门是一种长期在户外使用的设备,工作电压为220 V(过去也有380 V),其电机是处…...
stable diffusion安装踩坑之clip安装、git报错
clip本地安装环境链接问题 本节主要记录一下在windows安装stable diffusion时,clip脚本安装不上,本地安装时如何链接到当前库的问题 首先,在脚本安装clip不成功时,脚本会输出一个commend指令,复制到浏览器就可以很快…...
colmap gpu服务器安装
1.官方安装说明 https://colmap.github.io/install.html 后边有编译支持gpu的步骤!!! 2.sudo apt-get install libgtest-dev 3.cmakelists.txt 250行 set(CMAKE_CUDA_ARCHITECTURES “native”) 4. sudo apt-get install libqt5core5a sud…...
linux内的循环
格式 while 【 条件判断 】 do 语句体 done 上图 第一次代码,输入语句在外面,结果输入完(非hello)程序不断循环,没办法,ctrlc给程序终止了,然后把用户输入的语句放到了循环体里面…...
强化学习(RL)的学习笔记
1. 前言 (1)PPO的优点 PPO(Proximal Policy Optimization)算法相比其他强化学习方法有几个显著优点: 稳定性和鲁棒性:PPO通过限制策略更新的幅度来避免训练过程中的大幅波动,这增加了算法的稳…...
2023世界传感器大会开幕,汉威科技多领域创新产品引瞩目
11月5日,2023世界传感器大会在郑州国际会展中心正式拉开帷幕。据悉,本次大会由河南省人民政府、中国科学技术协会主办,郑州市人民政府、河南省工业和信息化厅、河南省科学技术协会、中国仪器仪表学会承办。 大会由“一会一赛一展”组成&#…...
什么是机器学习中的正则化?
1. 引言 在机器学习领域中,相关模型可能会在训练过程中变得过拟合和欠拟合。为了防止这种情况的发生,我们在机器学习中使用正则化操作来适当地让模型拟合在我们的测试集上。一般来说,正则化操作通过降低过拟合和欠拟合的可能性来帮助大家获得…...
PostgreSQL JDBC连接详解(附DEMO)
PostgreSQL JDBC连接详解 PostgreSQL JDBC连接详解摘要引言1. JDBC基础1.1 JDBC简介1.2 JDBC驱动程序1.3 建立JDBC连接 2. 配置PostgreSQL JDBC连接2.1 PostgreSQL连接JDBC2.2 PostgreSQL连接JDBC是否成功2.3 PostgreSQL连接JDBC获取表信息注释等2.4 PostgreSQL连接JDBC根据表名…...
学习视频剪辑:巧妙运用中画、底画,制作画中画,提升视频效果
随着数字媒体的普及,视频剪辑已经成为一项重要的技能。在视频剪辑过程中,制作画中画可以显著提升视频效果、信息传达和吸引力。本文讲解云炫AI智剪如何巧妙运用中画、底画批量制作画中画来提升视频剪辑水平,提高剪辑效率。 操作1、先执行云…...
Android Studio代码无法自动补全
Android Studio代码自动无法补全问题解决 在写layout布局文件时,代码不提示,不自动补全,可以采用如下方法: 点击File—>Project Structure,之后如图所示,找到左侧Modules,修改SDK版本号&…...
从零开始搭建微服务
人狠话不多,直接开始少点屁话本着共同学习进步的目的和大家交流如有不对的地方望铁子们多多谅解 准备工具 开发工具 idea Java环境 jdk.18 Maven 3.8.6 仓库镜像阿里云 <mirror><id>alimaven</id><name>aliyun maven</name><url>https:…...
HF Hub 现已加入存储区域功能
我们在 企业版 Hub 服务 方案中推出了 存储区域(Storage Regions) 功能。https://hf.co/enterprise 通过此功能,用户能够自主决定其组织的模型和数据集的存储地点,这带来两大显著优势,接下来的内容会进行简要介绍&…...
linux下实现电脑开机后软件自启动
实现linux的软件自启动,需要四个文件 第一个【displayScreen.desktop】文件,.desktop文件就是一个用来运行程序的快捷方式,也叫启动器,常用来自启动用的文件,内容如下 [Desktop Entry] #要执行的脚本位置 Exec/home/yicaobao/te…...
【C/PTA】循环结构进阶练习(二)
本文结合PTA专项练习带领读者掌握循环结构,刷题为主注释为辅,在代码中理解思路,其它不做过多叙述。 7-1 二分法求多项式单根 二分法求函数根的原理为:如果连续函数f(x)在区间[a,b]的两个端点取值异号,即f(a)f(b)<0…...
Visual Studio 2010 软件安装教程(附下载链接)——计算机二级专用编程软件
下载链接: 提取码:2wAKhttps://www.123pan.com/s/JRpSVv-9injv.html 安装步骤如下: 1.如图所示,双击打开【Visual Studio 2010简体中文旗舰版】文件夹 2.如图所示,找到“Setup”文件夹打开,双击运行“setup” 3.如图…...
大促来袭 零点价格如何监测
双十一大促即将到来,各大品牌、店铺都会非常关注价格,这个时候的促销信息会很复杂,平台促销、店铺促销等,不同的优惠信息涉及的券也会很多,同时各优惠券关联的时间点也会不同,有些券零点能用,有…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
