hdu1198 Farm Irrigation 并查集

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1198
简单并查集
分别合并竖直方向和水平方向即可
代码：
 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #define maxn 110
 6 using namespace std;
 7 int parent[maxn*maxn];
 8 char map[maxn][maxn];
 9 int find(int x)
10 {
11    int s;
12    for(s=x;parent[s]>=0;s=parent[s]);
13    while(s!=x)
14    {
15       int tmp=parent[x];
16       parent[x]=s;
17       x=tmp;
18    }
19    return s;
20 }
21 void Union(int r1,int r2)
22 {
23      int R1=find(r1);
24      int R2=find(r2);
25      int tmp=parent[R1]+parent[R2];
26      if(parent[R1]>parent[R2])
27      {
28           parent[R1]=R2;
29           parent[R2]=tmp;
30      }
31      else
32      {
33          parent[R2]=R1;
34          parent[R1]=tmp;
35      }
36 }
37 int main()
38 {
39     int  m,n;
40     while(scanf("%d%d",&m,&n)!=EOF)
41     {
42         if(m<0 || n<0) break;
43         for(int i=0;i<m;i++)
44          scanf("%s",map[i]);
45         for(int i=0;i<m*n;i++)
46         parent[i]=-1;
47         for(int i=0;i<m;i++)
48          for(int j=0;j<n;j++)
49          {
50             if(i>0 && (map[i][j]=='A' ||map[i][j]=='B'||map[i][j]=='E'||map[i][j]=='G'||map[i][j]=='H'||map[i][j]=='J'||map[i][j]=='K'))
51             if(map[i-1][j]=='C'||map[i-1][j]=='D'||map[i-1][j]=='E'||map[i-1][j]=='H'||map[i-1][j]=='I'||map[i-1][j]=='J'||map[i-1][j]=='K')
52             Union(i*n+j,(i-1)*n+j);
53             if(j>0&&(map[i][j]=='A'||map[i][j]=='C'||map[i][j]=='F'||map[i][j]=='G'||map[i][j]=='H'||map[i][j]=='I'||map[i][j]=='K'))
54             if(map[i][j-1]=='B'||map[i][j-1]=='D'||map[i][j-1]=='F'||map[i][j-1]=='G'||map[i][j-1]=='I'||map[i][j-1]=='J'||map[i][j-1]=='K')
55             Union(i*n+j,i*n+j-1);
56          
57         }
58         int ans=0;
59         for(int i=0;i<m*n;i++)
60         if(parent[i]<0) ans++;
61         cout<<ans<<endl;
62     }
63 return 0;
64 }