1 //hdu 1198 并查集
   2 //2009年5月20日16:50:13
   3 //题目大意：一块地需要浇水，而每块的都又16种不同的土地浇灌系统中的多块组成
   4 //          求不同种组合的浇灌系统组成的地需要多少个浇水机才能浇灌完成
   5 //解题思路：我使用的是并查集的方法，首先用一个一维数组begning[]来存储输入进来的farm样式
   6 //          再用farm[i][4]来表示这块地左上右下的联通情况，根据这和思想来判断这两块地是否连通
   7 //          最后用并查集思想来判断整块地被分成了几块！
   8 //自己出现的问题：我刚开始把begning和map的数组开得太小了
   9 //by zjd
  10 
  11 #include<stdio.h>
  12 #include<string>
  13 using namespace std;
  14 
  15 int farm[11][4]=
  16 {//左中右下 
  17 {1,1,0,0},
  18 {0,1,1,0},
  19 {1,0,0,1},
  20 {0,0,1,1},
  21 {0,1,0,1},
  22 {1,0,1,0},
  23 {1,1,1,0},
  24 {1,1,0,1},
  25 {1,0,1,1},
  26 {0,1,1,1},
  27 {1,1,1,1}       
  28 };
  29 
  30 int map[5000];
  31 int m,n;
  32 char c;
  33 int begning[5000];
  34 
  35 void Merge(int x,int y){
  36         int xx=x;
  37         int yy=y;
  38         while(map[xx]!=-1){
  39                 xx=map[xx];
  40         }
  41         while(map[yy]!=-1){
  42                 yy=map[yy];
  43         }
  44 
  45         int t;
  46         int i=x;
  47         while(map[i]!=-1){
  48                 t=map[i];
  49                 map[i]=xx;
  50                 i=t;
  51         }       
  52         int j=y;
  53         while(map[j]!=-1){
  54                 t=map[j];
  55                 map[j]=yy;
  56                 j=t;    
  57         }
  58         if(yy!=xx){
  59                 map[yy]=xx;     
  60         }
  61 }
  62 
  63 int main(){
  64         int i,j;
  65         while(scanf("%d%d",&m,&n)!=EOF&&(m!=-1&&n!=-1)){
  66                 getchar();
  67                 memset(map,-1,sizeof(map));
  68                 for(i=0;i<m;i++){
  69                         for(j=0;j<n+1;j++){
  70                                 c=getchar();
  71                                 if(c!='\n')
  72                                         begning[i*n+j]=c-'A';           
  73                         }
  74                 }
  75         for(i=0;i<m*n;i++){
  76                 if(((i%n)+1)<n&&farm[begning[i]][2]==farm[begning[i+1]][0]&&farm[begning[i]][2]==1)//当这块土地可以和右边那块土地合并时 
  77                         Merge(i,i+1);
  78                 if((i+n<m*n)&&farm[begning[i]][3]==farm[begning[i+n]][1]&&farm[begning[i]][3]==1)//当这块土地可以和下边那块土地合并时 
  79                         Merge(i,i+n);           
  80         }       
  81         int sum=0;
  82         for(i=0;i<m*n;i++){
  83                 if(map[i]==-1)
  84                 sum++;
  85         }
  86         printf("%d\n",sum);
  87         }
  88         return 0;
  89 }