【并查集】hdu 1198 Farm Irrigation

题目描述：

http://acm.hdu.edu.cn/showproblem.php?pid=1198

 

中文大意：

农田是一个矩形，被分成了若干个小正方形。

小正方形区域内，将会铺设上水管，用来灌溉农田。

现在，想知道，至少需要多少个泉源，才能将农田全部灌溉。

已知共有 11 种管道，从 A 到 K 标记。

水可以沿着管道从一个正方形流到另一个正方形。

思路：

尝试将相互流通的小正方形合并到一个集合。

最终，集合个数即为泉源个数。

 

代码：

#include<bits/stdc++.h>
using namespace std;

int m,n;
int maps[50][50];//水管类型 
int pre[2500];//各节点的所属集 
int height[2500];//各集合的树高 

//初始化 
void init(){
    for(int i=0;i<m*n;i++){
        pre[i] = i;
        height[i] = 1;
    }
} 

//每类水管在四个方向上（上左下右）的连通情况
//1表示连通，0表示不连通 
int dir[11][4] = {
{1,0,0,1},//A 
{1,1,0,0},//B
{0,0,1,1},//C
{0,1,1,0},//D
{1,0,1,0},//E
{0,1,0,1},//F
{1,1,0,1},//G
{1,0,1,1},//H
{0,1,1,1},//I
{1,1,1,0},//J
{1,1,1,1}};//K

//寻找节点 x 的所属集 
int find(int x){
    if(x == pre[x]){
        return x;
    }
    int root = find(pre[x]);
    pre[x] = root;
    return root;
}

//flag = 1,尝试连接同一行紧邻的水管
//flag = 2,尝试连接同一列紧邻的水管 
void union_set(int row, int col, int flag){
    //草地坐标 
    int r1,r2;
    if(flag == 1){
        r1 = row * n + col;
        r2 = row * n + col + 1;
        
        //获取水管类型 
        int x = maps[row][col];
        int y = maps[row][col+1];
        //两种水管在左右方向上不能连通 
        if(dir[x][1] == 0 || dir[y][3] == 0){
            return; 
        }
    }
    else{
        r1 = row * n + col;
        r2 = (row + 1) * n + col;
        
        int x = maps[row][col];
        int y = maps[row+1][col];
        //两种水管在上下方向上不能连通 
        if(dir[x][2] == 0 || dir[y][0] == 0){
            return;
        }
    }
        
    r1 = find(r1);
    r2 = find(r2);
    
    if(height[r1] == height[r2]){
        pre[r1] = r2;
        height[r2]++;
    }
    else if(height[r1] > height[r2]){
        pre[r2] = r1;
    }
    else{
        pre[r1] = r2;
    }
}

int main(){
    while(scanf("%d %d", &m, &n) && (m >= 0 || n >= 0)){
        init();
        string str;
        for(int i=0;i<m;i++){
            cin>>str;
            for(int j=0;j<n;j++){
                maps[i][j] = str[j] - 'A';
            }
        }
        //左右连通 
        for(int i=0;i<m;i++){
            for(int j=0;j<n-1;j++){
                union_set(i, j, 1);
            }
        }
        //上下连通 
        for(int j=0;j<n;j++){
            for(int i=0;i<m-1;i++){
                union_set(i, j, 2);
            }
        }
        //集合个数 
        int num = 0;
        for(int i=0;i<m*n;i++){
            if(i == pre[i]){
                num++;
            }
        } 
        printf("%d
", num);
    }
}