题目:http://acm.hdu.edu.cn/showproblem.php?pid=1198
有题目图11种土地块，块中的绿色线条为土地块中修好的水渠，现在一片土地由上述的各种土地块组成，需要浇水，问需要打多少口井
比如
ADC
FJK
IHE是下图这种情况
需要打三口井,其实想多了就是集合合并差不多,用并查集可以解决,将每个格子按顺序是从0到n*m-1,然后根据连接情况判断是否相连然后合并
第一次写成了下面这样,虽然一遍过了,但是觉得太长了,然后又改成了下下面简洁的
长的
1 #include<cstdio> 2 using namespace std; 3 int father[500*500+10]; 4 int n,m,a[5]; 5 char yj[550][550]; 6 void give(int x) 7 { 8 for (int i=0;i<x;i++) 9 father[i]=i; 10 } 11 int _find(int x) 12 { 13 if (x==father[x]) return father[x]; 14 father[x]=_find(father[x]); 15 return father[x]; 16 } 17 void jjc(int x,int sx) 18 { 19 for (int i=1;i<=x;i++){ 20 if (a[i]>=0&&a[i]<n*m) 21 { 22 int sa=_find(a[i]); 23 if (sa!=sx) 24 father[sa]=sx; 25 } 26 } 27 } 28 int main() 29 { 30 int i,j; 31 while (~scanf("%d %d",&n,&m)) 32 { 33 if (n==-1&&m==-1) break; 34 for (i=0;i<n;i++) 35 scanf("%s",yj[i]); 36 give(n*m); 37 for (i=0;i<n;i++) 38 { 39 for (j=0;j<m;j++) 40 { 41 int x=i*m+j; 42 int sx=_find(x); 43 if (yj[i][j]==‘A‘) 44 { 45 int k=1; 46 char op=yj[i-1][j]; 47 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 48 a[k++]=x-m; 49 op=yj[i][j-1]; 50 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 51 a[k++]=x-1; 52 if (k>1) jjc(k-1,sx); 53 } 54 else if (yj[i][j]==‘B‘) 55 { 56 int k=1; 57 char op=yj[i-1][j]; 58 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 59 a[k++]=x-m; 60 op=yj[i][j+1]; 61 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 62 a[k++]=x+1; 63 if (k>1) jjc(k-1,sx); 64 } 65 else if (yj[i][j]==‘C‘) 66 { 67 int k=1; 68 char op=yj[i][j-1]; 69 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 70 a[k++]=x-1; 71 op=yj[i+1][j]; 72 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 73 a[k++]=x+m; 74 if (k>1) jjc(k-1,sx); 75 } 76 else if (yj[i][j]==‘D‘) 77 { 78 int k=1; 79 char op=yj[i][j+1]; 80 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 81 a[k++]=x+1; 82 op=yj[i+1][j]; 83 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 84 a[k++]=x+m; 85 if (k>1) jjc(k-1,sx); 86 } 87 else if (yj[i][j]==‘E‘) 88 { 89 int k=1; 90 char op=yj[i-1][j]; 91 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 92 a[k++]=x-m; 93 op=yj[i+1][j]; 94 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 95 a[k++]=x+m; 96 if (k>1) jjc(k-1,sx); 97 } 98 else if (yj[i][j]==‘F‘) 99 { 100 int k=1; 101 char op=yj[i][j-1]; 102 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 103 a[k++]=x-1; 104 op=yj[i][j+1]; 105 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 106 a[k++]=x+1; 107 if (k>1) jjc(k-1,sx); 108 } 109 else if (yj[i][j]==‘G‘) 110 { 111 int k=1; 112 char op=yj[i][j-1]; 113 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 114 a[k++]=x-1; 115 op=yj[i-1][j]; 116 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 117 a[k++]=x-m; 118 op=yj[i][j+1]; 119 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 120 a[k++]=x+1; 121 if (k>1) jjc(k-1,sx); 122 } 123 else if (yj[i][j]==‘H‘) 124 { 125 int k=1; 126 char op=yj[i-1][j]; 127 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 128 a[k++]=x-m; 129 op=yj[i][j-1]; 130 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 131 a[k++]=x-1; 132 op=yj[i+1][j]; 133 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 134 a[k++]=x+m; 135 if (k>1) jjc(k-1,sx); 136 } 137 else if (yj[i][j]==‘I‘) 138 { 139 int k=1; 140 char op=yj[i][j-1]; 141 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 142 a[k++]=x-1; 143 op=yj[i][j+1]; 144 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 145 a[k++]=x+1; 146 op=yj[i+1][j]; 147 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 148 a[k++]=x+m; 149 if (k>1) jjc(k-1,sx); 150 } 151 else if (yj[i][j]==‘J‘) 152 { 153 int k=1; 154 char op=yj[i-1][j]; 155 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 156 a[k++]=x-m; 157 op=yj[i][j+1]; 158 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 159 a[k++]=x+1; 160 op=yj[i+1][j]; 161 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 162 a[k++]=x+m; 163 if (k>1) jjc(k-1,sx); 164 } 165 else if (yj[i][j]==‘K‘) 166 { 167 int k=1; 168 char op=yj[i-1][j]; 169 if (op==‘C‘||op==‘D‘||op==‘E‘||op==‘H‘||op==‘I‘||op==‘J‘||op==‘K‘) 170 a[k++]=x-m; 171 op=yj[i+1][j]; 172 if (op==‘A‘||op==‘B‘||op==‘E‘||op==‘G‘||op==‘H‘||op==‘J‘||op==‘K‘) 173 a[k++]=x+m; 174 op=yj[i][j-1]; 175 if (op==‘B‘||op==‘D‘||op==‘F‘||op==‘G‘||op==‘I‘||op==‘J‘||op==‘K‘) 176 a[k++]=x-1; 177 op=yj[i][j+1]; 178 if (op==‘A‘||op==‘C‘||op==‘F‘||op==‘G‘||op==‘H‘||op==‘I‘||op==‘K‘) 179 a[k++]=x+1; 180 if (k>1) jjc(k-1,sx); 181 } 182 //printf("%d\n",father[3]); 183 } 184 } 185 int sum=0; 186 for (i=0;i<n*m;i++) 187 { 188 if (father[i]==i) 189 { 190 sum++; 191 //printf("%d\n",i); 192 } 193 } 194 printf("%d\n",sum); 195 } 196 return 0; 197 }
比上面简洁的
1 #include<cstdio> 2 using namespace std; 3 char yj[550][550]; 4 int father[550*550+10]; 5 int dir[11][5]={{1,0,1,0},{1,0,0,1},{0,1,1,0}, 6 {0,1,0,1},{1,1,0,0},{0,0,1,1}, 7 {1,0,1,1},{1,1,1,0},{0,1,1,1}, 8 {1,1,0,1},{1,1,1,1}}; 9 void give(int x) 10 { 11 for (int i=0;i<x;i++) 12 father[i]=i; 13 } 14 int _find(int x) 15 { 16 if (x==father[x]) return father[x]; 17 father[x]=_find(father[x]); 18 return father[x]; 19 } 20 int merge(int x,int y) 21 { 22 int sx=_find(x); 23 int sy=_find(y); 24 if (sx!=sy) 25 father[sx]=sy; 26 } 27 int main() 28 { 29 int n,m,i,j; 30 while (~scanf("%d %d",&n,&m)) 31 { 32 if (n==-1&&m==-1) break; 33 for (i=0;i<n;i++) 34 scanf("%s",yj[i]); 35 give(n*m); 36 for (i=0;i<n;i++) 37 { 38 for (j=0;j<m;j++) 39 { 40 int x=yj[i][j]-‘A‘; 41 int y=yj[i][j+1]-‘A‘; 42 if (dir[x][3]==1&&dir[y][2]==1&&j+1<m) 43 merge(i*m+j,i*m+j+1); 44 y=yj[i+1][j]-‘A‘; 45 if (dir[x][1]==1&&dir[y][0]==1&&i+1<n) 46 merge(i*m+j,(i+1)*m+j); 47 } 48 } 49 int sum=0; 50 for (i=0;i<n*m;i++) 51 if (father[i]==i) 52 sum++; 53 printf("%d\n",sum); 54 } 55 return 0; 56 }
hdu 1198 (并查集的应用) Farm Irrigation
原文：http://www.cnblogs.com/JJCHEHEDA/p/4836637.html