Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 4802 Accepted
Submission(s): 2073
#include<iostream> #include<cstdio> #include<cstring> #define N 55 using namespace std; int n,m,f[N*N]; int map[55][55]; int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; int farm[11][4]={ {1,0,0,1}, {1,1,0,0}, {0,0,1,1}, {0,1,1,0}, {1,0,1,0}, {0,1,0,1}, {1,1,0,1}, {1,0,1,1}, {0,1,1,1}, {1,1,1,0}, {1,1,1,1} }; void init(){ for(int i=0; i<N*N; ++i)f[i]=i;} int findset(int x){ return f[x]!=x?f[x]=findset(f[x]):f[x];} void merge(int x,int y) { int a=findset(x), b=findset(y); if(a==b)return ; if(a<b) f[a]=b; else f[b]=a; } int main() { int i,j,k,dx,dy; char ch; while(scanf("%d%d%",&n,&m)) { if(n==-1 && m==-1) break; for(i=0; i<n; ++i) { for(j=0; j<m; ++j) { scanf("%c",&ch); map[i][j]=ch-‘A‘; } getchar(); } init(); for(i=0; i<n; ++i) { for(j=0; j<m; ++j) { for(k=0; k<4; ++k) { dx=i+dir[k][0],dy=j+dir[k][1]; if(dx<0||dx>=n||dy<0||dy>=m)continue; if(k==0)// 左 { if(farm[map[dx][dy]][1]&&farm[map[i][j]][3]){ merge(dx*m+dy, i*m+j); } } else if(k==1)// 上 { if(farm[map[dx][dy]][2]&&farm[map[i][j]][0]){ merge(dx*m+dy, i*m+j); } } else if(k==2)// 右 { if(farm[map[dx][dy]][3]&&farm[map[i][j]][1]){ merge(dx*m+dy, i*m+j); } } else if(k==3)// 下 { if(farm[map[dx][dy]][0]&&farm[map[i][j]][2]){ merge(dx*m+dy, i*m+j); } } } } } int cnt=0; for(i=0; i<n*m; ++i) if(f[i]==i) ++cnt; printf("%d\n", cnt); } return 0; }
原文:http://www.cnblogs.com/xiong-/p/3583456.html