题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5925
Coconuts
Memory Limit: 65536/65536 K (Java/Others)
输出
For each test case, output "Case #x:" in the first line, where x denotes the number of test case, one integer k in the second line, denoting the number of times TanBig needs, in the third line, k integers denoting the number of coconuts he would eat each time, you should output them in increasing order.
样例输入
2
3 3
2
1 2
2 1
3 3
1
2 2
样例输出
Case #1:
2
1 6
Case #2:
1
8
题意
给你一个n*m的网格，问障碍物把网格分割成多少个连通块，按从大到小的顺序输出每个连通块的大小。
题解
由于障碍就200多个，我们对障碍物离散化下，因为离散化不会影响被障碍物包围起来的连通块，所以离散化之后我们只统计被包围的那些（一个点事障碍物，要把它周围的点也离散化，否则会出现本来没被围起来的被围了），然后最后再算出外围的大块。
注意：在边缘的被分割开的连通块需要特殊处理下，这需要用到题目里面的一个提示：“the first row and the last row will not have bad coconuts at the same time, the first column and the last column will not have bad coconuts at the same time.”。我们标记下四周的状态，就可以判断我们统计的块是不是被夹在角落，还是离散化之后伪的被夹在角落。
代码
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=222;
int R,C,n,nn,mm;
PII pt[maxn];
int vis[maxn][maxn];
const int dx[]= {-1,1,0,0};
const int dy[]= {0,0,-1,1};
bool _flag[4];
LL bfs(int xs,int ys) {
queue<PII> Q;
LL res=1;
vis[xs][ys]=1;
Q.push(mkp(xs,ys));
int flag=0;
while(!Q.empty()) {
PII u=Q.front();
Q.pop();
int x=u.X,y=u.Y;
for(int i=0; i<4; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>nn||ny<1||ny>mm) {
if(nx<1&&_flag[0]==0) flag=1;
if(nx>nn&&_flag[1]==0) flag=1;
if(ny<1&&_flag[2]==0) flag=1;
if(ny>mm&&_flag[3]==0) flag=1;
continue;
}
if(!vis[nx][ny]) {
vis[nx][ny]=1;
res++;
Q.push(mkp(nx,ny));
}
}
}
if(flag) return 0;
return res;
}
int main() {
int tc,kase=0;
scf("%d",&tc);
while(tc--) {
scf("%d%d%d",&R,&C,&n);
VI ha_x,ha_y;
clr(_flag,0);
rep(i,0,n) {
scf("%d%d",&pt[i].X,&pt[i].Y);
//标记四周的状态，用于判断被围在边缘的情况
if(pt[i].X==1) _flag[0]=1;
if(pt[i].X==R) _flag[1]=1;
if(pt[i].Y==1) _flag[2]=1;
if(pt[i].Y==C) _flag[3]=1;
//离散化
if(pt[i].X-1>=1) ha_x.pb(pt[i].X-1);
ha_x.pb(pt[i].X);
if(pt[i].X+1<=R) ha_x.pb(pt[i].X+1);
if(pt[i].Y-1>=1) ha_y.pb(pt[i].Y-1);
ha_y.pb(pt[i].Y);
if(pt[i].Y+1<=C) ha_y.pb(pt[i].Y+1);
}
//离散化
sort(all(ha_x));
ha_x.erase(unique(all(ha_x)),ha_x.end());
sort(all(ha_y));
ha_y.erase(unique(all(ha_y)),ha_y.end());
nn=ha_x.sz();
mm=ha_y.sz();
//外围的那个联通块
LL Ma=(LL)R*C-n;
vector<LL> ans;
//离散化
clr(vis,0);
rep(i,0,n) {
pt[i].X=lower_bound(all(ha_x),pt[i].X)-ha_x.begin()+1;
pt[i].Y=lower_bound(all(ha_y),pt[i].Y)-ha_y.begin()+1;
vis[pt[i].X][pt[i].Y]=1;
}
prf("Case #%d:
",++kase);
LL sum=0;
//对于离散化的图暴力bfs
for(int i=1; i<=nn; i++) {
for(int j=1; j<=mm; j++) {
if(!vis[i][j]) {
LL res=bfs(i,j);
if(res) {
sum+=res;
ans.pb(res);
}
}
}
}
Ma-=sum;
if(Ma) ans.pb(Ma);
sort(all(ans));
prf("%d
",ans.sz());
rep(i,0,ans.sz()) {
prf("%lld",ans[i]);
if(i==ans.sz()-1) prf("
");
else prf(" ");
}
}
return 0;
}
//end-----------------------------------------------------------------------
/*
222
4 4
4
1 2
2 1
2 3
3 2
7 7
4
3 4
4 3
4 5
5 4
*/