題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1198

dfs：

1 #include<cstdio>//hdu1198 dfs 2 #include<cstring> 3 4 int well[11][5] = { {1,1,1,0,0},{1,0,1,1,0},{0,1,1,0,1},{0,0,1,1,1},{1,0,1,0,1},{0,1,1,1,0},{1,1,1,1,0},{1,1,1,0,1},{0,1,1,1,1},{1,0,1,1,1},{1,1,1,1,1}}; 5 6 const int ca[5][2] = {0,1,1,0,1,1,1,2,2,1}, mov[4][2] = {1,0,-1,0,0,1,0,-1}; 7 int m,n,sum, map[550][550],id[550][550]; 8 9 void build(int set, int x, int y) 10 { 11 for(int k = 0; k<5; k++) 12 { 13 if(well[set][k]) 14 { 15 map[3*x+ca[k][0]][3*y+ca[k][1]] = 1; 16 } 17 } 18 } 19 20 void dfs(int x, int y, int iden) 21 { 22 id[x][y] = iden; 23 for(int i = 0; i<4; i++) 24 { 25 int xx = x + mov[i][0], yy = y + mov[i][1]; 26 if(xx<0 || xx>3*m-1 || yy<0 || yy>3*n-1 ) continue; 27 if(map[xx][yy] && !id[xx][yy]) 28 dfs(xx,yy,iden); 29 } 30 } 31 32 int main() 33 { 34 char init[5005]; 35 while(scanf("%d%d",&m,&n) && (m!=-1 || n!=-1 )) 36 { 37 memset(map,0,sizeof(map)); 38 memset(id,0,sizeof(id)); 39 for(int i = 0; i<m; i++) 40 { 41 scanf("%s",init); 42 for(int j = 0; j<n; j++) 43 build(init[j]-65,i,j); 44 } 45 sum = 0; 46 for(int i = 0; i<=3*m-1; i++) 47 { 48 49 for(int j = 0; j<=3*n-1; j++) 50 { 51 //printf("%d ",map[i][j]); 52 if(map[i][j] && !id[i][j]) 53 { 54 dfs(i,j,++sum); 55 } 56 } 57 //putchar('\n'); 58 } 59 60 printf("%d\n",sum); 61 62 } 63 return 0; 64 } View Code

并查集：

1 #include<cstdio>//hdu1198 并查集 每個格子的標號為i*n+j，初始father也為i*n+j，以次來作為合并集合的依據 2 #include<cstring> 3 4 int n,m,father[55][55]; 5 char map[55][55]; 6 char type[11][5]={"1010","1001","0110","0101","1100","0011", 7 "1011","1110","0111","1101","1111"}; 8 9 int find(int x) 10 { 11 return (x==father[x/n][x%n])?x:find(father[x/n][x%n]); 12 } 13 14 int unit(int a, int b) 15 { 16 a = find(a); 17 b = find(b); 18 if(a!=b)//合并集合 19 father[a/n][a%n] = b; 20 } 21 22 23 int judge(int i, int j) 24 { //判斷是否與左邊相連 25 if(j>0 && type[map[i][j]-'A'][2]=='1' && type[map[i][j-1]-'A'][3]=='1') 26 unit(i*n+j,i*n+j-1); 27 //判斷是否與上邊相連 28 if(i>0 && type[map[i][j]-'A'][0]=='1' && type[map[i-1][j]-'A'][1]=='1') 29 unit(i*n+j,(i-1)*n+j); 30 } 31 32 int main() 33 { 34 while(scanf("%d%d",&m,&n) && (m!=-1 || n!=-1)) 35 { 36 for(int i = 0; i<m; i++) 37 { 38 scanf("%s",&map[i]); 39 for(int j = 0; j<n; j++) 40 { //初始化為自己 41 father[i][j] = i*n+j; 42 } 43 } 44 45 //并查集過程 46 for(int i = 0; i<m; i++) 47 for(int j = 0; j<n; j++) 48 judge(i,j); 49 50 int sum = 0; 51 for(int i = 0; i<m; i++) 52 for(int j = 0; j<n; j++)//看看有多少個“根節點” 53 if(father[i][j]==i*n+j) sum++; 54 55 printf("%d\n",sum); 56 } 57 58 } View Code

?

?

?

轉載于:https://www.cnblogs.com/DOLFAMINGO/p/7538774.html

總結

以上是生活随笔為你收集整理的hdu1198 Farm Irrigation —— dfs or 并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。