题意：一个图，n个障碍，求联通块
思路： 图很大，障碍物很少。把联通的障碍物块抠出来，然后暴力。
代码：
#include<bits/stdc++.h>
using namespace std;
#define MEM(a,b) memset(a,b,sizeof(a))
#define bug puts("bug");
#define PB push_back
#define MP make_pair
#define X first
#define Y second
typedef unsigned long long ll;
typedef pair<int,int> pii;
const int maxn=1e5+10;
const int mod=1000000007;
using namespace std;
int t,n,r,c,x,y,ca;
pii pp[maxn];
int dir[8][2]={1,0,1,-1,1,1,0,1,0,-1,-1,1,-1,0,-1,-1};
int dd[4][2]={1,0,0,1,0,-1,-1,0};
int mp[205][205],vp[205][205];
vector<ll> ans;
set<pii> vis,S;
int dfs(int x,int y,int mix,int miy,int mxx,int mxy){
int ret=1,tmp;
vp[x][y]=1;
for(int i=0;i<4;i++){
int xx=x+dd[i][0],yy=y+dd[i][1];
if(xx<0&&mix!=1) ret=-1;
if(yy<0&&miy!=1) ret=-1;
if(xx>mxx-mix&&mxx!=r) ret=-1;
if(yy>mxy-miy&&mxy!=c) ret=-1;
if(xx<0||yy<0||xx>mxx-mix||yy>mxy-miy||vp[xx][yy]||mp[xx][yy])continue;
tmp=dfs(xx,yy,mix,miy,mxx,mxy);
if(tmp==-1||ret==-1) ret=-1;
else ret+=tmp;
}
return ret;
}
void bfs(pii P){
queue<pii> Q;
Q.push(P);
vis.insert(P);
vector<pii> tp;
int mix=1e9+10,miy=1e9+10,mxx=-1,mxy=-1;
while(!Q.empty()){
pii t=Q.front();
mix=min(mix,t.X);miy=min(miy,t.Y);mxx=max(mxx,t.X);mxy=max(mxy,t.Y);
tp.PB(t);
Q.pop();
for(int i=0;i<8;i++){
pii nxt=MP(t.X+dir[i][0],t.Y+dir[i][1]);
if(!vis.count(nxt)&&S.count(nxt))Q.push(nxt),vis.insert(nxt);
}
}
MEM(mp,0);MEM(vp,0);
int ret=0;
for(int i=0;i<tp.size();i++) mp[tp[i].X-mix][tp[i].Y-miy]=1;
for(int i=0;i<=mxx-mix;i++)
for(int j=0;j<=mxy-miy;j++)
if(mp[i][j]==0&&vp[i][j]==0&&(ret=dfs(i,j,mix,miy,mxx,mxy))>0) ans.PB(ret);
return;
}
int main(){
for(cin>>t,ca=1;ca<=t;ca++){
S.clear(),vis.clear(),ans.clear();
cin>>r>>c>>n;
for(int i=0;i<n;i++) cin>>pp[i].X>>pp[i].Y,S.insert(pp[i]);
for(int i=0;i<n;i++) if(vis.count(pp[i])==0) bfs(pp[i]);
ll sum=(ll)r*c;
for(int i=0;i<ans.size();i++) sum-=ans[i];
ans.PB(sum-n);
sort(ans.begin(),ans.end());
cout<<"Case #"<<ca<<":
";
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++) cout<<ans[i]<<"
"[i==ans.size()-1];
}
return 0;
}