Gym

Gym - 102785B Gremlins attack!

题目：[https://vjudge.net/problem/Gym-102785B/origin]

题意：给一个n*n的矩阵，里面有m个小精灵想到边界去，但是只能走关了灯的地方，现在给你k个灯可以关闭的位置，给的顺序就是关的顺序，请问在关第几盏灯时至少有一个小精灵能出去，小精灵一在边界就等于出去了，如果开始时就有小精灵在边界，则输出零。

思路：用并查集把可以关灯的位置和它四个方向连起来，但是不是全部连，只有同样是可以关灯的位置或者是小精灵的位置可以连，然后设一个虚拟点start把小精灵和这个点都连上，再设一个虚拟点end表示出口，把边界上的关灯位置和这个点都连上。对于关灯位置边输入边执行以上操作，当getfa（start）=getfa（end）时，说明有小精灵可以出去，后面的灯都不用关了。

#include<bits/stdc++.h>
using namespace std;
#define mo 9901
#define ll long long
#define inf 0x7f7f7f
#define N 250010
ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ll)(ch-'0');ch=getchar();}
	return x*f;
}
int n,dad[N],a[505][505],sta,ed;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int m,k,ans;
bool check(int x,int y)
{
	if (x==0||y==0||x==n-1||y==n-1)
		return true;
	return false;
}
int getfa(int x)
{
	return x==dad[x]?x:dad[x]=getfa(dad[x]);
}
void link(int x,int y)
{
	int xx=getfa(x),yy=getfa(y);
	if (xx!=yy) dad[xx]=yy;
}
void uni(int x,int y)
{
	if (check(x,y)) link(x*n+y,ed);
	for (int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if (nx<0||ny<0||nx>n-1||ny>n-1) continue;
		if (a[nx][ny]==1) 
			link(x*n+y,sta);
		if (a[nx][ny]==2)
			link(x*n+y,nx*n+ny);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
	for (int i=0;i<=n*n+5;i++)
		dad[i]=i;
	ans=-1;
	sta=n*n+1,ed=n*n+2;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		if (check(x,y)) ans=0;
		a[x][y]=1;
	}
	for (int i=1;i<=k;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=2;
		if (ans!=-1) continue;
		uni(x,y);
		if (getfa(sta)==getfa(ed))
			ans=i;
	}
	cout<<ans<<endl;
	return 0;
}