HDU1198 Farm Irrigation

题意：给如一个地图，每一个方块上都有一条河流，如果两个方块间的河流连接在一起，那他们就是同一条河流。每条河流必须有一个源点。这样才能保证每条河流所在的方块上的农田能被灌溉到。

简化一下提议，就是求有多少条河流。

思路：从给出的11块方块种类，可以计算两块农田一上下或者左右连在一起是否能构成一条河流，如果能，就用并查集连在一起，最后计算有多少个节点就OK了。

思路简单，代码不做注释！

#include<iostream>
    using namespace std;
    #define MAXN 505
    struct Farm {
        bool up;
        bool down;
        bool left;
        bool right;
    }farms[MAXN];
    int father[MAXN * MAXN];
    int findSet(int a) {
        if (a == father[a]) {
            return a;
        } else {
            return findSet(father[a]);
        }
    }
    void Union(int a,int b) {
        int x = findSet(a);
        int y = findSet(b);
        if (x == y) {
            return;
        }
        father[y] = x;
        return;
    }
    int findRoot(int n) {
        int count = 0;
        for (int i=0; i<n; i++) {
            if (father[i] == i) {
                count ++;
            }
        }
        return count;
    }
    void init() {
        for (int i=0; i<MAXN*MAXN; i++) {
            father[i] = i;
        }

        farms[0].up = 1;
        farms[0].left = 1;

        farms[1].up = 1;
        farms[1].right = 1;

        farms[2].left = 1;
        farms[2].down = 1;

        farms[3].right = 1;
        farms[3].down = 1;

        farms[4].up = 1;
        farms[4].down = 1;

        farms[5].left = 1;
        farms[5].right = 1;

        farms[6].left = 1;
        farms[6].up = 1;
        farms[6].right = 1;

        farms[7].left = 1;
        farms[7].up = 1;
        farms[7].down = 1;

        farms[8].left = 1;
        farms[8].down = 1;
        farms[8].right = 1;

        farms[9].up = 1;
        farms[9].right = 1;
        farms[9].down = 1;

        farms[10].left = 1;
        farms[10].right = 1;
        farms[10].up = 1;
        farms[10].down = 1;
    }
    char map[MAXN][MAXN];
    int main() {
        int n, m;
        while (cin>>n>>m) {
            if (n == -1 && m == -1) {
                break;
            }
            init();
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    cin>>map[i][j];
                }
            }
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if ((i - 1) >= 0) {
                        if (farms[map[i-1][j]-'A'].down && farms[map[i][j]-'A'].up) { 
                            int x = i * m + j;
                            int y = (i - 1) * m + j;
                            Union(x, y);
                        } 
                    }
                    if ((i + 1) < n) {
                        if (farms[map[i+1][j]-'A'].up && farms[map[i][j]-'A'].down) {
                            int x = i * m + j;
                            int y = (i + 1) * m + j;
                            Union(x, y);
                        } 
                    }
                    if ((j - 1) >= 0) {
                        if (farms[map[i][j-1]-'A'].right && farms[map[i][j]-'A'].left) {
                            int x = i * m + j;
                            int y = i * m + (j - 1);
                            Union(x, y);
                        } 
                    }
                    if ((j + 1) < m) {
                        if (farms[map[i][j+1]-'A'].left && farms[map[i][j]-'A'].right) {
                            int x = i * m + j;
                            int y = i * m + (j + 1);
                            Union(x, y);
                        } 
                    }
                }
            }
            cout<<findRoot(n * m)<<endl;

        }
    }