Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用并查集,相当水,一次AC#include<stdio.h> int set[2501],num[2501],map[51][51]; void init(int x) { set[x]=x; num[x]=1; } int find(int x) { if(set[x]==x)return x; return set[x]=find(set[x]); } void _union(int a,int b) { int x1=find(a); int x2=find(b); if(x1==x2) return; if(num[x1]>num[x2]) { set[x2]=x1; num[x1]+=num[x2]; } else { set[x1]=x2; num[x2]+=num[x1]; } } int main() { int m,n; scanf("%d%d",&m,&n); int i,j,dir; for(i=0;i<n*m;i++)init(i); for(i=0;i<m;i++) for(j=0;j<n;j++) { scanf("%d",&dir); if(dir%2==0&&j>0) _union(i*n+j,i*n+j-1); if((dir>>1)%2==0&&i>0) _union(i*n+j,(i-1)*n+j); if((dir>>2)%2==0&&j<n-1) _union(i*n+j,i*n+j+1); if((dir>>3)%2==0&&i<m-1) _union(i*n+j,(i+1)*n+j); } int cnt=1,max=num[find(0)]; for(i=1;i<m*n;i++) { int a1=find(i),a2=find(i-1); if(a1!=a2) { cnt++; if(num[a1]>max) max=num[a1]; _union(a1,a2); } } printf("%d\n%d\n",cnt,max); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator