题意：一张n*m的网格图（n和m可以达到10^9），其中K个点是障碍物（不超过200个），问你没有被障碍物占据的点形成了几个连通块？并且输出各个连通块的大小。
容易证明，大小超过40000的连通块最多只有一个。于是可以从每个与障碍物邻接的非障碍点出发bfs，限制步数不超过40000，这样就可以找到所有小的连通块。最后如果n*m-K-小的连通块的总大小不等于0，则剩下的就是那个大的连通块的大小。
用map打标记进行判重。
#include<cstdio>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> Point;
const int dx[]={0,-1,0,1,1,-1,1,-1},dy[]={-1,0,1,0,-1,-1,1,1};
const int dx1[]={0,-1,0,1},dy1[]={-1,0,1,0};
Point p[205];
int T,m,n,K;
int main(){
scanf("%d",&T);
for(int zu=1;zu<=T;++zu){
map<Point,int>vis;
set<Point>za;
vector<ll>vs;
printf("Case #%d:\n",zu);
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=K;++i){
scanf("%d%d",&p[i].first,&p[i].second);
za.insert(p[i]);
}
int bj=0;
for(int i=1;i<=K;++i){
int x=p[i].first,y=p[i].second;
for(int j=0;j<8;++j){
int tx=x+dx[j],ty=y+dy[j];
if(tx>=1 && tx<=n && ty>=1 && ty<=m){
if(za.find(Point(tx,ty))==za.end()){
if(!vis[Point(tx,ty)]){
++bj;
queue<Point>q;
q.push(Point(tx,ty));
vis[Point(tx,ty)]=bj;
int cnt=1;
bool flag=1;
while(!q.empty()){
Point U=q.front();
q.pop();
for(int k=0;k<4;++k){
int ttx=U.first+dx1[k],tty=U.second+dy1[k];
if(ttx>=1 && ttx<=n && tty>=1 && tty<=m && za.find(Point(ttx,tty))==za.end()){
int tmp=vis[Point(ttx,tty)];
if(tmp>0 && tmp<bj){
flag=0;
break;
}
else if(tmp==0){
q.push(Point(ttx,tty));
++cnt;
vis[Point(ttx,tty)]=bj;
if(cnt>40000){
flag=0;
goto OUT;
}
}
}
}
}
OUT:
if(flag){
vs.push_back((ll)cnt);
}
}
}
}
}
}
ll sum=0;
for(vector<ll>::iterator it=vs.begin();it!=vs.end();++it){
sum+=(*it);
}
if((ll)n*(ll)m>sum+(ll)K){
vs.push_back((ll)n*(ll)m-sum-(ll)K);
}
sort(vs.begin(),vs.end());
int sz=vs.size();
printf("%d\n",sz);
for(int i=0;i<sz;++i){
printf("%lld",vs[i]);
if(i==sz-1){
puts("");
}
else{
putchar(' ');
}
}
}
return 0;
}