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（总结）

谢谢