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

Time Limit: 2000/1000 MS (java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4991Accepted Submission(s): 2143

題目大意：給定農田的水管的走向，如果兩塊農田有水管能夠互相連通，則它們是相連的，水流能通過兩塊農田。要你求出最少需要挖多少口井（水井在每塊農田的正中央），才能使所有農田都被灌溉。根據上圖例子，需要3口水井就能將所有農田都被灌溉。

分析：這道題有兩種方法可以做，第一種是簡單dfs，第二種是并查集，dfs如果不懂的同學就要去普及搜索知識了。并查集的話同樣，求連通區域的個數，如果兩塊農田連通，則它們在一個等價類中，最后求等價類個數。

dfs方法實現如下，首先要對11個農田狀態進行標記，個人標記的方法各不相同，可以使用二維數組存儲，這里我用結構體表示更為直觀：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 struct farm 7 { 8     bool left,right,top,bottom; 9     farm()10     {11         left=right=top=bottom=false;12     }13 }FM[13];14 char mp[55][55];15 bool vis[55][55];16 int n, m;17 void init()18 {19     FM[0].left=FM[0].top=true;20     FM[1].right=FM[1].top=true;21     FM[2].left=FM[2].bottom=true;22     FM[3].right=FM[3].bottom=true;23     FM[4].top=FM[4].bottom=true;24     FM[5].left=FM[5].right=true;25     FM[6].left=FM[6].right=FM[6].top=true;26     FM[7].left=FM[7].top=FM[7].bottom=true;27     FM[8].left=FM[8].right=FM[8].bottom=true;28     FM[9].top=FM[9].right=FM[9].bottom=true;29     FM[10].left=FM[10].right=FM[10].top=FM[10].bottom=true;30 }31 void dfs(int x, int y)32 {33     vis[x][y] = true;34     int c  = mp[x][y]-'A';35     if(x-1>=0 && FM[c].top && FM[mp[x-1][y]-'A'].bottom && !vis[x-1][y])36         dfs(x-1, y);37     if(y-1>=0 && FM[c].left && FM[mp[x][y-1]-'A'].right && !vis[x][y-1])38         dfs(x, y-1);39     if(x+1 < m && FM[c].bottom &&  FM[mp[x+1][y]-'A'].top && !vis[x+1][y])40         dfs(x+1, y);41     if(y+1 < n && FM[c].right && FM[mp[x][y+1]-'A'].left && !vis[x][y+1])42         dfs(x, y+1);43 }44 int main()45 {46     init();47     while(cin >> m >> n)48     {49         if(m<0 || n<0) break;50         for(int i = 0; i < m; i++)51             for(int j = 0; j < n; j++)52                 cin >> mp[i][j];53         memset(vis, false,sizeof(vis));54         int sum = 0;55         for(int i = 0; i < m; i++)56             for(int j = 0; j < n; j++)57                 if(!vis[i][j])58                 {59                     sum++;60                     dfs(i, j);61                 }62         printf("%d/n", sum);63     }64     return 0;65 }

并查集方法，將二維坐標轉化為一維，對每塊農田找左、上連通情況，合并等價類，關于等價類更多知識，請讀者補充知識：

#include <iostream>#include <cstdio>#include <cstring>using namespace std;int F[3100];char mp[55][55];int m, n;char pipe[11][5] = {"1100", "0110", "1001", "0011", "0101",    "1010", "1110", "1101", "1011", "0111", "1111"};int Find(int x){    if(F[x] == -1) return x;    return Find(F[x]);}void Union(int x, int y){    int t1 = Find(x);    int t2 = Find(y);    if(t1 != t2)        F[t1] = t2;}int main(){    while(scanf("%d%d", &m, &n))    {        if(m<0 || n<0) break;        for(int i = 0; i < m; i++)                scanf("%s", &mp[i]);        memset(F, -1, sizeof(F));        for(int i = 0; i < m; i++)            for(int j = 0; j < n; j++)            {                if(i>0 && pipe[mp[i][j]-'A'][1]=='1' && pipe[mp[i-1][j]-'A'][3]=='1')                    Union(i*n+j, (i-1)*n+j);                if(j>0 && pipe[mp[i][j]-'A'][0]=='1' && pipe[mp[i][j-1]-'A'][2]=='1')                    Union(i*n+j, i*n+j-1);            }        int cnt = 0;        for(int i = 0; i < m*n; i++)            if(F[i] == -1)                cnt++;        printf("%d/n", cnt);    }    return 0;}