学步园

题目：Farm Irrigation

这题很不错的，给的图片让人想不到是并查集，我第一次做的时候用dfs()过的，最近在看并查集，才知道并查集也可以做。关键在于如何建图，如何找到相连关系。对每张图片分析就会知道，每块地的水管都是在中间，分为上、下、左、右四个方向可以通水，分两种模式，一种水平相邻，一种竖直相邻，判断他们能不能相通，先预处理得到每两个字符所代表的土地的关系，读入数据后，对应处理，将每块地都编一个标号，就抽象出并查集模型了，最后判断一下有几个点，它的根节点是它自己，就能找到最少需要的水源了。这也是并查集应用之一：判断有几个不相交的集合。

 

#include<stdio.h>
#include<string.h>

int up[8], down[8], right[8], left[8];
int rank[2504], bin[2504];
char map[54][54];
char mat1[100][100]; // 上下相连
char mat2[100][100]; // 左右相连
void prepare()
{
int i, j;
    up[0] = 'A'; up[1] = 'B'; up[2] = 'E'; up[3] = 'G'; up[4] = 'H'; up[5] = 'J'; up[6] = 'K';
    down[0] = 'C'; down[1] = 'D'; down[2] = 'E'; down[3] = 'H'; down[4] = 'I'; down[5] = 'J'; down[6] = 'K';
    left[0] = 'A'; left[1] = 'C'; left[2] = 'F'; left[3] = 'G'; left[4] = 'H'; left[5] = 'I'; left[6] = 'K';
    right[0] = 'B'; right[1] = 'D'; right[2] = 'F'; right[3] = 'G'; right[4] = 'I'; right[5] = 'J'; right[6] = 'K';
    memset(mat1, 0, sizeof(mat1));
    memset(mat2, 0, sizeof(mat2));
for (i = 0; i <= 6; i++){
for (j = 0; j <= 6; j++){
            mat1[down[i]][up[j]] = 1;
            mat2[right[i]][left[j]] = 1;
        }
    }
}

int find(int x){
if (x != bin[x]){
return bin[x] = find(bin[x]);
    }
return x;
}

void merge(int x, int y){
int fx, fy;
    fx = find(x);
    fy = find(y);

if (fx != fy){
if (rank[fx] > rank[fy]){
            bin[fy] = fx;
        }else if (rank[fx] < rank[fy]){
            bin[fx] = fy;
        }else{
            bin[fx] = fy;
            rank[fy]++;
        }
    }
}

int main()
{
int M, N, i, j, t1, t2, cnt;
    prepare();
while (scanf("%d%d", &M, &N) != EOF){
if (M == -1 && N == -1) break;
for (i = 0; i < M; i++){
            scanf("%s", map[i]);
        }

for (i = 0; i <= M * N; i++){
            bin[i] = i;
            rank[i] = 0;    
        }
for (i = 0; i < M; i++){
for (j = 0; j < N; j++){
if (j < N - 1 && mat2[map[i][j]][map[i][j+1]] == 1){
                    t1 = i * N + j;
                    t2 = i * N + j + 1;
                    merge(t1, t2);
                }

if (i < M - 1 && mat1[map[i][j]][map[i + 1][j]] == 1){
                    t1 = i * N + j;
                    t2 = (i + 1) * N + j;
                    merge(t1, t2);
                }
            }
        }

        cnt = 0;
for (i = 0; i < M * N; i++){
if (bin[i] == i){
                cnt++;
            }
        }

        printf("%d\n", cnt);
    }
return 0;
}

这里用的递归法压缩路径，感觉也挺好的，代码很短，以前都是用非递归形式。在合并的时候，按秩合并很重要，每次合并，总把深度小的树合并到深度大的树里面，以防止树退化成链。这样可以减少树的深度，使得查找时间很均匀，更高效的查找。