hdu 1198 Farm Irrigation

hdu 1198 的传送门

Sample Input

2 2
DK
HF
3 3
ADC
FJK
IHE

-1 -1 

Sample Output

2
3

题目大意：有如上图11种土地块，块中的绿色线条为土地块中修好的水渠，现在一片土地由上述的各种土地块组成，需要浇水，问需要打多少口井。
解题思路：用并查集，注意要初始化就好了

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
//记录水管的形状，每种水管用一个由'0'和'1'组成的长度为4的字符串代表,
//分别表示上下左右四边是否有接口，'0'无，'1'有  

char pipe[11][5]={"1010","1001","0110","0101","1100","0011",
               "1011","1110","0111","1101","1111"};

int fa[55][55];
char map[55][55];
int m, n;

int Find(int x)//查找父亲节点，压缩路径
{
    if(fa[x/n][x%n] != x)
        fa[x/n][x%n] = Find(fa[x/n][x%n]);
    return fa[x/n][x%n];
}

void Union(int x, int y)//合并 x 和 y
{
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy)
        fa[fy/n][fy%n] = fx;
}

void judge(int i, int j))//判断map[i][j]和它的左侧和上侧是否连通,如连通则合并
{
    if(j>0 && pipe[map[i][j]-'A'][2]=='1' && pipe[map[i][j-1]-'A'][3]=='1')
        Union(i*n+j,i*n+j-1);

    if(i>0 && pipe[map[i][j]-'A'][0]=='1' && pipe[map[i-1][j]-'A'][1]=='1')
        Union(i*n+j,(i-1)*n+j);
}

int main()
{
    while(~scanf("%d%d",&m, &n))
    {
        if(m==-1 && n==-1)
            break;
        for(int i=0; i<m; i++)
        {
            scanf("%s",map[i]);
            for(int j=0; j<n; j++)
                fa[i][j]=i*n+j;//将父亲结点初始化
        }

        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                judge(i, j);

        int cnt=0;//统计几个集合
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(fa[i][j] == i*n+j)
                    cnt++;
        printf("%d\n",cnt);
    }
    return 0;
}