hdu 1198 (并查集 or dfs) Farm Irrigation

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1198

有题目图11种土地块，块中的绿色线条为土地块中修好的水渠，现在一片土地由上述的各种土地块组成，需要浇水，问需要打多少口井

比如

ADC
FJK
IHE是下图这种情况

需要打三口井,其实想多了就是集合合并差不多,用并查集可以解决,将每个格子按顺序是从0到n*m-1,然后根据连接情况判断是否相连然后合并

第一次写成了暴力的,虽然一遍过了,但是觉得太长了,然后又改成了下面简洁并查集的,还有下下面的dfs的

并查集

 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
",sum);
54     }
55     return 0;
56 }

dfs

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int dx[5]={1,-1,0,0};//下上左右
 5 int dy[5]={0,0,-1,1};
 6 char yj[550][550];
 7 int ans,vis[550][550],n,m;
 8 int dir[11][5]={{1,0,1,0},{1,0,0,1},{0,1,1,0},
 9                 {0,1,0,1},{1,1,0,0},{0,0,1,1},
10                 {1,0,1,1},{1,1,1,0},{0,1,1,1},
11                 {1,1,0,1},{1,1,1,1}};
12 int check(int x,int y,int di)
13 {
14     if (dir[x][0]&&dir[y][1]&&di==0) return 1;
15     if (dir[x][1]&&dir[y][0]&&di==1) return 1;
16     if (dir[x][3]&&dir[y][2]&&di==2) return 1;
17     if (dir[x][2]&&dir[y][3]&&di==3) return 1;
18     return 0;
19 }
20 void dfs(int x,int y)
21 {
22     int i;
23     if (vis[x][y]) return;
24     vis[x][y]=1;
25     //printf("%d %d
",x,y);
26     for (i=0;i<4;i++)
27     {
28         int sx=x+dx[i];
29         int sy=y+dy[i];
30         if (sx<0||sx>=n||sy<0||sy>=m) continue;
31         if (vis[sx][sy]) continue;
32         int q=yj[sx][sy]-'A';
33         int w=yj[x][y]-'A';
34         if (check(q,w,i))
35             dfs(sx,sy);
36     }
37 }
38 int main()
39 {
40     int i,j;
41     while (~scanf("%d %d",&n,&m))
42     {
43         if (n==-1&&m==-1) break;
44         for (i=0;i<n;i++)
45             scanf("%s",yj[i]);
46         memset(vis,0,sizeof(vis));
47         ans=0;
48         for (i=0;i<n;i++)
49         {
50             for (j=0;j<m;j++)
51             {
52                 if (vis[i][j]) continue;
53                 dfs(i,j);
54                 ans++;
55             }
56         }
57         printf("%d
",ans);
58     }
59     return 0;
60 }

hdu 1198 (并查集 or dfs) Farm Irrigation

相关推荐