ZJU2412 Farm Irrigation - 水管連通

題目描述：

有A-K共11種不同的水管，每個水管的連通方向不同。給出一個M×N的田地水管圖，求出最少需要多少個出水口可以灌溉全部田地。 原題 ZJU2412 

分析：

粗略一看，此題可以用搜尋算法來做。即尋找一共有多少個連通分量。

求圖有多少連通分量，一個很高效的方法是用并查集。此題也可以用并查集來解決。

對于地圖中每個格子，判斷它的水管能否與其上面和左面的格子連通。若能，則并在一起。

最後統計并查集中有多少連通分支即可。

代碼，0.00s

#include <stdio.h>

#define N 51

#define id(i,j) (i*m+j+1)

int dir[][2]={{-1,0},{0,-1}}; //up down

int link[][4]={  {1,0,1,0},{1,1,0,0}  //A B

                ,{0,0,1,1},{0,1,0,1}  //C D

                ,{1,0,0,1},{0,1,1,0}  //E F

                ,{1,1,1,0},{1,0,1,1}  //G H

                ,{0,1,1,1},{1,1,0,1}  //I J

                ,{1,1,1,1}};          //K

int f[N*N],m,n;

char map[N][N],ch;

int x,y,u,v,p,q,t;

int connect(int u,int v,int e){

    if(!e){ //up down

        if(link[u][0]&&link[v][3]) return 1;

        else return 0;

    }

    else{  //left right

        if(link[u][2]&&link[v][1]) return 1;

        else return 0;

    }

}

int root(int p){

    q=p;

    while(f[q]) q=f[q];

    while(f[p]){

        t=f[p];

        f[p]=q;

        p=t;

    }

    return q;

}

void work(int i,int j,int e){

    x=i+dir[e][0];

    y=j+dir[e][1];

    u=map[i][j];

    v=map[x][y];

    if(connect(u,v,e)){

        p=root(id(i,j));

        q=root(id(x,y));

        if(p!=q) f[p]=q;

    }

}

int main()

{

    int i,j,k,ans;

    while(scanf("%d%d",&n,&m),m!=-1||n!=-1)

    {

        //input

        getchar();

        for(i=0;i<n;i++){

            for(j=0;j<m;j++){

                scanf("%c",&ch);

                map[i][j]=ch-'A';

            }

            getchar();

        }

        //init

        for(i=0;i<=n*m;i++) f[i]=0;

        //work

        for(i=0;i<n;i++){

            for(j=0;j<m;j++){

                if(i) work(i,j,0);  //up

                if(j) work(i,j,1);  //left

            }

        }

        //count

        ans=0;

        for(i=0;i<n;i++)

            for(j=0;j<m;j++){

                k=id(i,j);

                if(root(k)==k) ans++;

            }

        //output

        printf("%d/n",ans);

    }

    return 0;

}