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.如图…...
大促来袭 零点价格如何监测
双十一大促即将到来,各大品牌、店铺都会非常关注价格,这个时候的促销信息会很复杂,平台促销、店铺促销等,不同的优惠信息涉及的券也会很多,同时各优惠券关联的时间点也会不同,有些券零点能用,有…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
