C题被我水了,提供一个hack数据
6 3 4
5 2
4 3
3 1
1 0
如下代码能过
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3010;
int x[N],y[N];
int f[N];
int find(int c){
if(f[c]==c)return c;
return f[c]=find(f[c]);
}
void unite(int a,int b){
a=find(a);b=find(b);
if(a==b)return;
f[a]=b;
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=k+1;i++)f[i]=i;
for(int i=1;i<=k;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=1;i<=k;i++){
if(x[i]==0||y[i]==m)unite(0,i);
if(y[i]==0||x[i]==n)unite(k+1,i);
}
int T=1;
while(T--){
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
if(abs(x[i]-x[j])<=1&&abs(y[i]-y[j])<=1)unite(i,j);
if(find(k+1)==find(i)&&x[i]<x[j]&&y[j]<=y[i]+1)unite(i,j);
if(find(0)==find(i)&&y[i]<y[j]&&x[j]<=x[i]+1)unite(i,j);
}
}
}
if(find(0)==find(k+1))printf("No");
else printf("Yes");
return 0;
}
查看2道真题和解析