HDU 1198 Farm Irrigation

题意：

给你一个N*M的矩阵，由下面11种格子组成，每个格子互联的部分不同(比如A如果放在C正下面，那么A与C是连通的)，问你所给矩阵一共有几个连通分量。

ADC
FJK
IHE

then the water pipes are distributed like

现在，每个测试案例中，先输入M，N，接着在接下来的M行中，每行输入N个范围在A-K的字母，要求求连通分量有几个。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define MAXN 2500
 4 int uset[MAXN];
 5 
 6 int Find(int x){return uset[x]==x?x:uset[x]=Find(uset[x]);}
 7 
 8 void makeSet(int x,int y){
 9     int fx=Find(x),fy=Find(y);
10     if(fx!=fy)
11         uset[fy]=fx;
12 }
13 int state[11][4]={1,1,0,0,1,0,0,1,0,1,1,0,0,0,1,1,1,0,1,0,
14                 0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1};
15 int main()
16 {
17     int m,n;
18     while(~scanf("%d%d",&m,&n)){
19         getchar();
20         if(m==-1)   break;
21 
22         char field[51][51];
23         int ans=0;
24 
25         for(int i=0;i<m;i++)
26             scanf("%s",&field[i]);
27 
28         for(int i=0;i<m*n;i++) uset[i]=i;
29 
30         for(int i=0;i<m;i++)
31             for(int j=0;j<n-1;j++){
32 
33                 int x=field[i][j]-'A',y=field[i][j+1]-'A';
34                 if(state[x][3]&&state[y][1])
35                     makeSet(i*n+j,i*n+j+1);
36             }
37         for(int i=0;i<m-1;i++)
38             for(int j=0;j<n;j++){
39 
40                 int x=field[i][j]-'A',y=field[i+1][j]-'A';
41                 if(state[x][2]&&state[y][0])
42                     makeSet(i*n+j,(i+1)*n+j);
43             }
44         for(int i=0;i<m*n;i++)
45             if(uset[i]==i)    ans++;
46         printf("%d
",ans);
47 
48     }
49 
50     return 0;
51 }

常规并查集题，13行，用state二维数组来保存A-K的连通状况，索引时，用字母减去字符A即可，其中每行有四个变量，分别代表该块地上，左，下，右方向是否连通，1表示连通。

31，37两组循环，分别意味着除最后一列，每列和右边一列的元素进行检查；除最后一行，每行和下一行元素进行检查。

同时注意makeSet传入的内容。

时间复杂度应该是O(mn)，不过数据规模很小，无关紧要啦。