2020.03.11模拟赛15(第四题)_SSL_LKJ的博客-程序员宅基地

技术标签: 赛后分析  

4.房间开灯(light)

题目描述

Farmer John 最近正在修建一个巨大的包含 N×N 个房间的牲口棚,这些房间从(1,1)标号到(N,N)。由于某些原因而害怕黑暗,贝茜这头奶牛想要尽可能地开更多房间的灯。贝茜从房间(1,1)出发,这个房间是唯一一个一开始就亮着的房间。在一些房间中,她会找到一些电灯开关,这些开关她可以用来切换其他房间的灯的状态。比如,在(1,1)这个房间中可能存在一个电灯开关来控制(1,2)房间中的电灯。贝茜只能进电灯开着的房间,并且贝茜只能从房间(x,y)走到四个方向的房间(x-1,y),(x+1,y),(x,y-1)和(x,y+1)(如果在边界的话,那可能会更少)。请帮忙统计贝茜最多可以照亮多少房间。

输入

第一行两个整数 N,M(2<=N<=100,1<=M<=20,000)
下面 M 行,每行用四个整数 x,y,a,b 来表示房间(x,y)存在着可以控制房间(a,b)的灯的开关。一个房间可能有多个开关,一个房间的灯的开关可能存在于多个房间中。

输出

一行一个整数,表示贝茜最多可以照亮的房间数

样例输入

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

样例输出

5
提示

在这个样例中,贝茜可以使用房间(1,1)内的开关打开房间(1,2)和(1,3)的灯。然后她可以走到(1,3),使用(1,3)内的开关打开(2,1)的灯,接着可以通过(2,1)打开(2,2)的灯,然而(2,3)是黑暗的,她无法去打开(2,3)房间里的开关,因此,她最多只能打开 5个房间里的灯。

正解
一个bfs就OK了
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y,h,t,s,x1,y1,tot;
int xx[20005],yy[20005],b[105][105],c[105][105],head[105][105];
int dx[5]={
    0,1,-1,0,0};
int dy[5]={
    0,0,0,1,-1};
struct node
{
    
	int tox,toy,next;
}a[20005];
void add(int x,int y,int x1,int y1)//邻接表
{
    
	tot++;
	a[tot].tox=x1;
	a[tot].toy=y1;
	a[tot].next=head[x][y];
	head[x][y]=tot;
}
void bfs()
{
    
	b[1][1]=1;//标记是否出现过
	c[1][1]=1;//1代表房间亮着
	xx[1]=1;//存x坐标
	yy[1]=1;//存y坐标
	t=1;
	while(h<t)
	{
    
		h++;
		for(int i=head[xx[h]][yy[h]];i;i=a[i].next)//邻接表
		 c[a[i].tox][a[i].toy]=1;//开灯
		for(int i=1;i<=h;i++)
		 for(int j=1;j<=4;j++)
		 {
    
			int xxx=xx[i]+dx[j],yyy=yy[i]+dy[j];
			if(xxx>=1&&xxx<=n&&yyy>=1&&yyy<=n)//边界
			 if(c[xxx][yyy]==1&&b[xxx][yyy]==0)//亮着并且没有被标记就进入
		     {
    
			 	b[xxx][yyy]=1;//标记
			 	t++;
			 	xx[t]=xxx;//记录
			 	yy[t]=yyy;
			 }
		 } 
	}
}
int main()
{
    
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
    
		cin>>x>>y>>x1>>y1;
		add(x,y,x1,y1);//有向
	}
	bfs();
	for(int i=1;i<=n;i++)//暴力一遍看有多少个房间亮着
	 for(int j=1;j<=n;j++)
	  if(c[i][j]==1)s++;
	cout<<s;  
	return 0;
}

下面附本次比赛的其它题目

2020.03.11模拟赛15(第一题)
2020.03.11模拟赛15(第二题)
2020.03.11模拟赛15(第三题)
2020.03.11模拟赛15(第四题)
2020.03.11模拟赛15(总结)

谢谢

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45524309/article/details/104979491

智能推荐

C语言关于数组与指针内容小结_Loving_初衷的博客-程序员宅基地

数组的基本概念什么是数组:数组就是:数组是相同类型的元素的一个集合       类型说明符 数组名 [常量表达式];其中,类型说明符是任一种基本数据类型或构造数据类型。数组名是用户定义的数组标识符。方括号中的常量表达式表示数据元素的个数,也称为数组的长度。例如:int a[10]; /* 说明整型数组a,有10个元素 */float b[10], c[20]; /* 说明实

Android动画归纳整理_胡小明同学的博客-程序员宅基地

Android 平台提供了两类动画。 一类是Tween动画,就是对场景里的对象不断的进行图像变化来产生动画效果(旋转、平移、放缩和渐变)。第二类就是 Frame动画,即顺序的播放事先做好的图像,与gif图片原理类似。 下面就讲一下Tweene Animations。 主要类: Animation   动画AlphaAnimation

Python学习速记一基础语法_weixin_33951761的博客-程序员宅基地

《Python语言及其应用》的学习笔记一、Python基本元素:数字、字符串和变量Python基本数据类型(不可变): bool, int, float, str1. 变量变量名只能包含大小写字母、数字、下划线,开头不能为数字type()检查对象的类型: type('hello') # &lt;class 'str'&gt;2. 数字常见运算: +, -, *, /(浮点数...

jvisualvm安装Visual GC插件_独家技术的博客-程序员宅基地

给jdk自带的jvisualvm安装Visual GC插件,遇到We're sorry the java.net site has closed(我们很抱歉java.net网站已经关闭)1、找到新的更新地址visualvm新访问地址:https://visualvm.github.io/index.html进入“Plugins”,找到对应自己JDK版本的更新地址2、进入jvisualvm的插件管理"工具" - "插件"在"设置"中修改url地址为刚才我们在github上找到的

vue2.0 + iview 表单验证明明有值却提示错误_weixin_34146805的博客-程序员宅基地

明明有值却总是提示为空我的解决方法时将number转为字符串验证方法如图:(验证只可以输入数字)赋值时转为字符串:转载于:https://www.cnblogs.com/xll-qg/p/9117777.html...

VM虚拟机安装Ubuntu18.04.2_胖毁青春,瘦解百病的博客-程序员宅基地

1.安装VMware Workstation Pro和Ubuntu 18.04.2 LTS   调整分辨率为:1280*800 16:10   安装中文语言2.安装VIM   sudo apt install vim3.为root设置密码   sudo passwd root 4.安装sshd   sudo apt-get install openssh-server5.安装i...

随便推点

java中定时器使用_snowing1997的博客-程序员宅基地_java定时器怎么使用

Java中定时器的书写。本文主要介绍了两种定时器的使用方式。一种是Spring框架自带的定时器【非常简单】,另一种是依赖第三方的定时器【较复杂,但是分工明确】

OpenYurt 深度解读|开启边缘设备的云原生管理能力_阿里云云原生的博客-程序员宅基地

作者|贾燚星(VMware), 何淋波(阿里云)北京时间 9 月 27 号,OpenYurt 发布 v0.5.0 版本。新发布版本中首次提出 kubernetes-native非侵入、可扩展的边缘设备管理标准,使 Kubernetes 业务负载模型和 IOT 设备管理模型无缝融合。同时联合 VMware 推动 EdgeX Foundry 作为云原生设备管理模型的首个实现并成功落地,大大降低 EdgeX Foundry 在 Kubernetes 上的部署管理的复杂度同时也提升了边缘设备的管理效率。云原生生

浅谈ANR及如何分析解决ANR_lalalalala的博客-程序员宅基地

(1)什么是ANR           ANR:Application Not Responding,即应用无响应(2)ANR的类型          ANR一般有三种类型:a:KeyDispatchTimeout(5 seconds) --主要类型,按键或触摸事件在特定时间内无响应。A key or touch event was not dispatched wit

Open××× 分配固定IP_weixin_33850890的博客-程序员宅基地

Open××× 分配固定IPOpen××× 分配固定IP修改server.conf 添加一行:client-config-dir /usr/local/open***-2.1.3/client添加客户端固定IPcat &gt; /usr/local/open***-2.1.3/client/selbooifconfig-push 192.168.70.117 192.168.70.118Ct...

多组学整合2连发,肠道研究新突破:人参残渣有大用_菌小落的博客-程序员宅基地

最近,派森诺与中国农业科学院特产研究所合作,在《Food Chemistry》和《Journal of Functional Foods》相继发表论文,通过高通量测序、代谢组检测结合生理实验分析,对喂食人参水溶性膳食纤维(SDF)后的实验大鼠状态进行记录,并检测其肠道菌群与代谢物以及各种生理指标,从微生物组、代谢物和生理指标三大角度研究了SDF对机体的作用。一、研究背景人参作为典型的食药两用植物,其生理活性的发现和确证一直是科研工作者的研究重点。人参膳食纤维(DF)是一种不能被人体消化的碳水化合物,被称

《C Primer Plus》,269页勘误,程序异常_Geometryolife的博客-程序员宅基地

269页程序清单10.19 flc.c程序有错误。下面展示第二种修改方法:

推荐文章

热门文章

相关标签