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

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"点的数目。如图所示&#xff0c;在10*10的二维数组中&#xff0c;"1"围住了15个点&#xff0c;因此面积为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环境集成套件包&#xff0c;安装完成后即可得到一个Nginx MyS…...

2023版Pycharm关闭一直显示closing project,正在关闭项目

点击 帮助 下的 查找操作 英文版为 Help 下的 Find Action 输入 Registry 禁用 ide.await.scope.completion 即可 PS&#xff1a;按 Ctrl F 输入可以快速检索...

Gradle笔记 二 Gradle的基础Groovy

学习Groovy的必要性 首先Gradle是由Groovy写成的&#xff0c;而且构建脚本的语法都遵循Groovy的语法&#xff0c;所以要学好Gradle的前提是要基本了解Groovy的语法。 Groovy 简介 在某种程度上&#xff0c;Groovy可以被视为Java的一种脚本化改良版,Groovy也是运行在JVM上&am…...

浅谈剩余电流动作继电器在电动伸缩门的应用

摘 要&#xff1a;随着时代的发展&#xff0c;越来越多的小区、厂区、园区和学校等场所的大门安装了电动伸缩门&#xff0c;几乎可以说随处可见。电动伸缩门是一种长期在户外使用的设备&#xff0c;工作电压为220 V&#xff08;过去也有380 V&#xff09;&#xff0c;其电机是处…...

stable diffusion安装踩坑之clip安装、git报错

clip本地安装环境链接问题 本节主要记录一下在windows安装stable diffusion时&#xff0c;clip脚本安装不上&#xff0c;本地安装时如何链接到当前库的问题 首先&#xff0c;在脚本安装clip不成功时&#xff0c;脚本会输出一个commend指令&#xff0c;复制到浏览器就可以很快…...

colmap gpu服务器安装

1.官方安装说明 https://colmap.github.io/install.html 后边有编译支持gpu的步骤&#xff01;&#xff01;&#xff01; 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 上图 第一次代码&#xff0c;输入语句在外面&#xff0c;结果输入完&#xff08;非hello&#xff09;程序不断循环&#xff0c;没办法&#xff0c;ctrlc给程序终止了&#xff0c;然后把用户输入的语句放到了循环体里面…...

强化学习(RL)的学习笔记

1. 前言 &#xff08;1&#xff09;PPO的优点 PPO&#xff08;Proximal Policy Optimization&#xff09;算法相比其他强化学习方法有几个显著优点&#xff1a; 稳定性和鲁棒性&#xff1a;PPO通过限制策略更新的幅度来避免训练过程中的大幅波动&#xff0c;这增加了算法的稳…...

2023世界传感器大会开幕,汉威科技多领域创新产品引瞩目

11月5日&#xff0c;2023世界传感器大会在郑州国际会展中心正式拉开帷幕。据悉&#xff0c;本次大会由河南省人民政府、中国科学技术协会主办&#xff0c;郑州市人民政府、河南省工业和信息化厅、河南省科学技术协会、中国仪器仪表学会承办。 大会由“一会一赛一展”组成&#…...

什么是机器学习中的正则化?

1. 引言 在机器学习领域中&#xff0c;相关模型可能会在训练过程中变得过拟合和欠拟合。为了防止这种情况的发生&#xff0c;我们在机器学习中使用正则化操作来适当地让模型拟合在我们的测试集上。一般来说&#xff0c;正则化操作通过降低过拟合和欠拟合的可能性来帮助大家获得…...

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根据表名…...

学习视频剪辑:巧妙运用中画、底画,制作画中画,提升视频效果

随着数字媒体的普及&#xff0c;视频剪辑已经成为一项重要的技能。在视频剪辑过程中&#xff0c;制作画中画可以显著提升视频效果、信息传达和吸引力。本文讲解云炫AI智剪如何巧妙运用中画、底画批量制作画中画来提升视频剪辑水平&#xff0c;提高剪辑效率。 操作1、先执行云…...

Android Studio代码无法自动补全

Android Studio代码自动无法补全问题解决 在写layout布局文件时&#xff0c;代码不提示&#xff0c;不自动补全&#xff0c;可以采用如下方法&#xff1a; 点击File—>Project Structure&#xff0c;之后如图所示&#xff0c;找到左侧Modules&#xff0c;修改SDK版本号&…...

从零开始搭建微服务

人狠话不多,直接开始少点屁话本着共同学习进步的目的和大家交流如有不对的地方望铁子们多多谅解 准备工具 开发工具 idea Java环境 jdk.18 Maven 3.8.6 仓库镜像阿里云 <mirror><id>alimaven</id><name>aliyun maven</name><url>https:…...

HF Hub 现已加入存储区域功能

我们在 企业版 Hub 服务 方案中推出了 存储区域&#xff08;Storage Regions&#xff09; 功能。https://hf.co/enterprise 通过此功能&#xff0c;用户能够自主决定其组织的模型和数据集的存储地点&#xff0c;这带来两大显著优势&#xff0c;接下来的内容会进行简要介绍&…...

linux下实现电脑开机后软件自启动

实现linux的软件自启动&#xff0c;需要四个文件 第一个【displayScreen.desktop】文件&#xff0c;.desktop文件就是一个用来运行程序的快捷方式,也叫启动器&#xff0c;常用来自启动用的文件&#xff0c;内容如下 [Desktop Entry] #要执行的脚本位置 Exec/home/yicaobao/te…...

【C/PTA】循环结构进阶练习(二)

本文结合PTA专项练习带领读者掌握循环结构&#xff0c;刷题为主注释为辅&#xff0c;在代码中理解思路&#xff0c;其它不做过多叙述。 7-1 二分法求多项式单根 二分法求函数根的原理为&#xff1a;如果连续函数f(x)在区间[a,b]的两个端点取值异号&#xff0c;即f(a)f(b)<0…...

Visual Studio 2010 软件安装教程(附下载链接)——计算机二级专用编程软件

下载链接&#xff1a; 提取码:2wAKhttps://www.123pan.com/s/JRpSVv-9injv.html 安装步骤如下&#xff1a; 1.如图所示&#xff0c;双击打开【Visual Studio 2010简体中文旗舰版】文件夹 2.如图所示&#xff0c;找到“Setup”文件夹打开&#xff0c;双击运行“setup” 3.如图…...

大促来袭 零点价格如何监测

双十一大促即将到来&#xff0c;各大品牌、店铺都会非常关注价格&#xff0c;这个时候的促销信息会很复杂&#xff0c;平台促销、店铺促销等&#xff0c;不同的优惠信息涉及的券也会很多&#xff0c;同时各优惠券关联的时间点也会不同&#xff0c;有些券零点能用&#xff0c;有…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...