HDU_1198 Farm Irrigation(并查集)

　　

/*
开始思路想错了，直接用并查集把输入的square并到并查集里边了，后来想到可能一种
square连续出现多次，这样直接合并肯定会出问题的。然后就一直再想其他思路，昨晚睡觉时突
然想到可以给这些square重新编号，把对应的square的pipes type继承过来，然后再用
并查集合并。最终以6A告终。不容易啊，大牛鄙视我吧。
*/

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 3000;

class pipes
{
    public:
        int l;        //左边节
        int r;        //右边界
        int u;        //上边界
        int d;        //下边界
}tmp[12], num[N];

int parent[N];
int rank[N];
int map[55][55];

void init()    //记录11种 pipes type。
{
    for(int i = 1; i <= 11; i++)
    {
        tmp[i].l = 0;
        tmp[i].r = 0;
        tmp[i].u = 0;
        tmp[i].d = 0;
    }

    tmp[1].l = 1;
    tmp[1].u = 1;

    tmp[2].r = 1;
    tmp[2].u = 1;

    tmp[3].l = 1;
    tmp[3].d = 1;

    tmp[4].r = 1;
    tmp[4].d = 1;

    tmp[5].u = 1;
    tmp[5].d = 1;

    tmp[6].l = 1;
    tmp[6].r = 1;

    tmp[7].l = 1;
    tmp[7].r = 1;
    tmp[7].u = 1;

    tmp[8].l = 1;
    tmp[8].u = 1;
    tmp[8].d = 1;

    tmp[9].l = 1;
    tmp[9].r = 1;
    tmp[9].d = 1;

    tmp[10].u = 1;
    tmp[10].r = 1;
    tmp[10].d = 1;

    tmp[11].l = 1;
    tmp[11].r = 1;
    tmp[11].u = 1;
    tmp[11].d = 1;
}

int find(int x)        //并查集非递归路径压缩查找，个人习惯这样写，因为递归的路径压缩可能会Ovre Stack(只是可能，大牛勿喷。。。)
{
    int k, r, j;
    r = x;
    while(r != parent[r])
        r = parent[r];
    k = x;
    while(k != r)
    {
        j = parent[k];
        parent[k] = r;
        k = j;
    }
    return r;
}

void Union(int a, int b)    //合并
{
    int x = find(a);
    int y = find(b);

    if(x == y)    return;

    if(rank[x] > rank[y])
        parent[y] = x;
    else
    {
        parent[x] = y;
        if(rank[x] == rank[y])
            ++rank[y];
    }
}

int main()
{
    //freopen("data.in", "r", stdin);

    int n, m;
    init();
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(n < 0 || m < 0)
            break;
        getchar();
        char c;
        int x = 1, t, i, j;    
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
            {
                scanf("%c", &c);
                t = c-'A'+1;
                map[i][j] = x;        //重新编号，起始号为1
                num[x].l = tmp[t].l;    //继承对应的 pipes type
                num[x].r = tmp[t].r;
                num[x].u = tmp[t].u;
                num[x].d = tmp[t].d;
                x++;
            }
            getchar();
        }

        /*for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
                printf("%d ", map[i][j]);
            printf("\n");
        }*/

        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
            {
                parent[map[i][j]] = map[i][j];         //初始化parent[],rank[];
                rank[map[i][j]] = 0;
            }
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
            {
                if(num[map[i][j]].l == num[map[i][j-1]].r && num[map[i][j]].l != 0 && j > 1)        //左边
                    Union(map[i][j], map[i][j-1]);
                    
                if(num[map[i][j]].r == num[map[i][j+1]].l && num[map[i][j]].r != 0 && j+1 <= m)        //右边
                    Union(map[i][j], map[i][j+1]);
                
                if(num[map[i][j]].u == num[map[i-1][j]].d && num[map[i][j]].u != 0 && i > 1)        //上边
                    Union(map[i][j], map[i-1][j]);
            
                if(num[map[i][j]].d == num[map[i+1][j]].u && num[map[i][j]].d != 0 && i+1 <= n)        //下边
                    Union(map[i][j], map[i+1][j]);
            }
        }
        int cnt = 0;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
                if(find(map[i][j]) == map[i][j])    //统计个数
                    cnt++;
        printf("%d\n", cnt);
    }
    return 0;
}