#142. 【UER #5】万圣节的南瓜灯
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://uoj.ac/problem/142
Description
这时候一群熊孩子们敲开了红包家的门,他们高呼着“不用给糖,只要捣蛋”的口号把红包的南瓜灯弄坏了。这让红包很难过,于是他打算把这些被弄坏的南瓜灯做成其他的工艺品。
红包把它的南瓜灯划分成了 n×m 的网格,并用 (x,y) 表示第 x 行,第 y 列的格子。两个格子是相邻的当且仅当它们有一条公共边,特殊地, (x,1) 和 (x,m) 红包也视为是相邻的,但是他不把 (1,x) 和 (n,x) 当做是相邻的。
对于一个有 K 个格子被弄坏的南瓜灯,如果它能被制作成工艺品,当且仅当对于任意两个没有被弄坏的格子,都存在且仅存在一条连接它们的简单路径。一条简单路径定义为一个只包含没有被弄坏的格子的序列 A1 至 An ,其中对于任意的 1≤i<n 都有 Ai 和 Ai+1 是相邻的,且每一个格子在序列中至多出现了一次。
现在红包有 T 个南瓜灯,他想让你帮他分别判断每一个南瓜灯能不能被做成工艺品。
Input
第一行一个正整数 T,表示南瓜灯数目。
对于每一个南瓜灯,第一行是三个整数 n,m,K,表示南瓜灯的大小和被弄坏的格子数。
接下来 K 行每行包含两个整数 x,y(1≤x≤n,1≤y≤m),表示第 x 行第 y 列的格子被弄坏了。
数据保证 n,m≥3,0≤K<nm 且不会重复描述一个被弄坏的格子。
Output
对于每一个南瓜灯,输出一行,如果这个南瓜灯能被做成工艺品,那么输出 "Yes",否则输出 "No"。
Sample Input
3 3 4
2 1
2 3
3 1
3 3
3 3 5
1 1
1 2
2 1
3 1
3 2
3 3 4
1 1
2 2
2 3
3 3
Sample Output
No
Yes
No
HINT
题意
给你一个网格,然后有些地方是墙,然后问你空出来的地方,是否能够构成一颗树
注意,左右是相连的
题解:
就暴力就好了,注意如果n*m>3e5 是可以直接判断为no的
所以这个可以拿到很多测试点
代码
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define maxn 1005000
int n,m,k,x,y;
int fa[maxn];
int vis[maxn];
int fi(int x)
{
return fa[x]==x?x:fa[x]=fi(fa[x]);
}
int flag = ;
int tot = ;
void uni(int x,int y)
{
int p = fi(x);
int q = fi(y);
if(p==q)
flag=;
if(p!=q)
{
fa[p]=q;
tot++;
}
}
int get(int x,int y)
{
long long p = x*m-m+y;
return p>?:p;
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
tot = ;
memset(vis,,sizeof(vis));
scanf("%d%d%d",&n,&m,&k);
if(1ll*n*m>){puts("No");for(int i=;i<=k;i++)scanf("%d%d",&x,&y);continue;}
for(int i=;i<=k;i++)
{
scanf("%d%d",&x,&y);
vis[get(x,y)]=;
}
for(int i=;i<=n*m;i++)
fa[i]=i;
flag = ;
for(int i=;i<=n*m;i++)
{
if(vis[i]==)
{
if(i%m==&&!vis[i-m+])
uni(i-m+,i);
if(i%m!=&&!vis[i-])
uni(i-,i);
if(i>m&&!vis[i-m])
uni(i-m,i);
if(flag)break;
}
if(flag)break;
}
if(flag||tot+!=n*m-k)
printf("No\n");
else
puts("Yes");
}
}