Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-14 const int N=1e3+500,M=4e6+10,inf=1e9+10,mod=1e9+7; const ll INF=1e18+10; int n,m,q; struct point { int x,y; }a[N]; ll l[N]; int getpos(int x,int flag) { return lower_bound(l,l+flag,x)-l; } int mp[N][N]; int vis[N][N]; int xx[4]={0,1,0,-1}; int yy[4]={-1,0,1,0}; int flag; int nn,mm; int check(int x,int y) { if(x<0||x>nn||y<0||y>mm) return 0; return 1; } void dfs(int n,int m,int deep) { vis[n][m]=deep; for(int i=0;i<4;i++) { int xxx=n+xx[i]; int yyy=m+yy[i]; if(check(xxx,yyy)&&!mp[xxx][yyy]&&!vis[xxx][yyy]) { dfs(xxx,yyy,deep); } } } ll ans[100010]; ll getnum(int x) { if(x==0) return l[x]; return l[x]-l[x-1]; } int main() { int T,cas=1; scanf("%d",&T); while(T--) { flag=0; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); int kuai=1; scanf("%d%d",&n,&m); scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d%d",&a[i].x,&a[i].y); l[flag++]=a[i].x; l[flag++]=a[i].y; if(a[i].x+1<=n) l[flag++]=a[i].x+1; if(a[i].y+1<=m) l[flag++]=a[i].y+1; if(a[i].x-1) l[flag++]=a[i].x-1; if(a[i].y-1) l[flag++]=a[i].y-1; } l[flag++]=1; if(n>=2||m>=2) l[flag++]=2; l[flag++]=n; l[flag++]=m; sort(l,l+flag); flag=unique(l,l+flag)-l; for(int i=1;i<=q;i++) { mp[getpos(a[i].x,flag)][getpos(a[i].y,flag)]=1; } nn=getpos(n,flag); mm=getpos(m,flag); for(int i=0;i<=nn;i++) { for(int t=0;t<=mm;t++) { if(!mp[i][t]&&!vis[i][t]) { dfs(i,t,kuai++); } } } for(int i=0;i<=nn;i++) { for(int t=0;t<=mm;t++) { if(vis[i][t]) { ans[vis[i][t]]+=getnum(i)*getnum(t); } } } printf("Case #%d:\n",cas++); printf("%d\n",kuai-1); if(kuai-1) { sort(ans+1,ans+kuai); printf("%lld",ans[1]); for(int i=2;i<kuai;i++) printf(" %lld",ans[i]); printf("\n"); } } return 0; }
原文:http://www.cnblogs.com/jhz033/p/5940406.html