題目鏈接：
http://acm.hdu.edu.cn/showproblem.php?pid=1198
題目大意：
有一大塊土地需要澆水，這塊土地由很多的小塊土地（有十一種）組成，小塊土地上有水溝，問至少需要建幾個井，才能灌溉這一大片土地？
11種土地，編號從A--K,
解題思路：
這個題目可以用很多種方法，可以用并查集，找出一共有多少個集合，也可以用dfs求連通塊，方法并不難，重在模型的轉化，我用4個0/1數字代表一塊土地，
并查集代碼：
1 #include <stdio.h> 2 #include <string.h> 3 #define N 25010 4 int a[N]; 5 int b[15][5] = {{1,1,0,0},{0,1,1,0},{1,0,0,1},{0,0,1,1,},{0,1,0,1},{1,0,1,0},{1,1,1,0},{1,1,0,1},{1,0,1,1},{0,1,1,1},{1,1,1,1,}}; 6 7 int cha (int i) 8 { 9 if ( a[i] != i ) 10 return cha ( a[i] ); 11 return i; 12 } 13 14 int main () 15 { 16 int i, j, n, m, num, x, y; 17 char map[55][55]; 18 while ( scanf ("%d %d", &n, &m), m > 0 && n > 0 ) 19 { 20 for (i=0; i<n; i++) 21 { 22 getchar (); 23 for (j=0; j<m; j++) 24 scanf ("%c", &map[i][j]); 25 } 26 for (i=0; i<n*m; i++) 27 a[i] =i; 28 for (i=0; i<n; i++) 29 for (j=0; j<m; j++) 30 { 31 if (i - 1 >= 0) 32 { 33 if ( b[ map[i-1][j]-'A' ][3] && b[ map[i][j]-'A' ][1] ) 34 { 35 x = cha ( (i-1)*m+j ); 36 y = cha ( i*m+j ); 37 if (x != y) 38 a[x] = a[y]; 39 } 40 } 41 if (j - 1 >= 0) 42 { 43 if ( b[ map[i][j-1]-'A' ][2] && b[ map[i][j]-'A' ][0] ) 44 { 45 x = cha ( i*m+j-1 ); 46 y = cha ( i*m+j ); 47 if (x != y) 48 a[x] = y; 49 } 50 } 51 } 52 num = 0; 53 for (i=0; i<n*m; i++) 54 if ( a[i] == i ) 55 num ++; 56 printf ("%d\n", num); 57 } 58 return 0; 59 }
bfs求連通塊代碼：
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 #define maxn 105 8 9 int G[maxn][maxn], M, N; 10 int v[maxn][maxn]; 11 12 int dir[4][2]={ {-1,0},{0,1},{1,0},{0,-1}}; 13 int f[4] = {2, 3, 0, 1}; 14 int dir1[11][4] = 15 { 16 {1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0}, 17 {1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1}, 18 {0,1,1,1},{1,1,1,0},{1,1,1,1} 19 }; 20 21 void DFS(int i, int j) 22 { 23 int nx, ny, k; 24 25 v[i][j] = -1; 26 27 for(k=0; k<4; k++) 28 { 29 nx = dir[k][0] + i; 30 ny = dir[k][1] + j; 31 int p = f[k]; 32 if( nx>=0&&nx<M && ny>=0&&ny<N && !v[nx][ny] && dir1[ G[i][j] ][k] && dir1[ G[nx][ny] ][p]) 33 { 34 DFS(nx, ny); 35 } 36 } 37 } 38 39 int main() 40 { 41 while(scanf("%d%d", &M, &N), M != -1) 42 { 43 int i, j, ans = 0; 44 char ch; 45 46 memset(v, 0, sizeof(v)); 47 48 for(i=0; i<M; i++) 49 for(j=0; j<N; j++) 50 { 51 cin >> ch; 52 G[i][j] = ch - 'A'; 53 } 54 55 for(i=0; i<M; i++) 56 for(j=0; j<N; j++) 57 { 58 if(v[i][j] == 0) 59 { 60 DFS(i, j); 61 ans++; 62 } 63 } 64 cout << ans <<endl; 65 } 66 67 return 0; 68 }
?
)
