hdu 1198 Farm Irrigation

点击打开hdu 1198

思路: 并查集
分析:
1 题目给定11快小方形，然后给定一个n*m的描述求n*m矩阵内的连通分量的个数
2 首先我们应该解决怎么保存11块小方形，我们可以利用一个思维的分量来描述，比如A我们描述成{1,0,0,1}
3 那么我们就可以做到在线进行并查集的操作，对于[i,j]这个方块，它可能和[i-1,j]和[i,j-1]进行相连，那么用i*m+j来唯一表示一个位置，那么最后枚举整个二维矩阵即可

代码:

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 55;
const int MAXN = 10000;

int n , m;
int father[MAXN];
char mat[N][N];
int state[11][4] = 
{{1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},{1,0,1,0},{0,1,0,1},
    {1,1,0,1},{1,0,1,1},{0,1,1,1},{1,1,1,0},{1,1,1,1}};

void init(){
    for(int i = 0 ; i < MAXN ; i++)
        father[i] = i;
}

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

void Union(int x , int y){
    int fx = find(x);    
    int fy = find(y);    
    father[fx] = fy;
}

void output(){
    set<int> s;
    for(int i = 0 ; i < n ; i++)
        for(int j =  0 ; j < m ; j++)
            s.insert(find(i*m+j));
    printf("%d\n" , s.size());
}

int main(){
    char ch;
    while(scanf("%d%d%*c" , &n , &m) && n > 0){
        init();   
        for(int i = 0 ; i < n ; i++){
            for(int j =  0 ; j < m ; j++){
                scanf("%c" , &mat[i][j]); 
                ch = mat[i][j];
                int x = ch-'A';
                if(i && state[x][0] == 1){
                   int y = mat[i-1][j]-'A'; 
                   if(state[x][0] == state[y][2])
                      Union(i*m+j , (i-1)*m+j);
                }
                if(j && state[x][3] == 1){
                   int y = mat[i][j-1]-'A'; 
                   if(state[x][3] == state[y][1])
                      Union(i*m+j , i*m+j-1);
                }
            } 
            getchar();
        }
        output();
    }
    return 0;
}