HDU 5652 India and China Origins(并查集)

本文链接:http://i.cnblogs.com/EditPosts.aspx?postid=5397634

题意：

　　中国和印度之间有一片地方，把这片地方抽象化，于是就可以看成一个N * M矩阵，其中黑色的代表高山不能走过去，白色的代表平原,可以

通行,人每次可以选择往上下左右四个方向移动,但是随着时间的变化某些白色的平原会变成黑色的高山，从而变为不可通行，题目中给出一个代表

地势的图，然后有 Q 次操作第 i 次操作代表在第 i 年(x, y)处的平原变成了高山,即白色变为了黑色。问中国印度最早彻底断绝的时间,如果在 Q

年后还没有断绝就输出 -1；

思路：

刚开始做的时候一看到图求图的连通性，很自然的用回溯了，这道题用二分 + 回溯，二分 + BFS都能做出来，但是后面觉得还是并查集好理

解点，就用并查集又写了一遍，用并查集的思想是如果上下彻底断绝联系，那么说明从左到右存在一片区域，或者一条线，都是由黑色的方格组

成,我们可以在为最左边开辟一个新的节点，最右边也开辟一个新的节点,如果这俩个节点某一时刻在一个集合里面了那么说明就已经彻底断绝了.

我的方法是：题目中给的图下标是(0 -- N - 1, 0 - -M - 1),我在这里用　(1 -- N,1 -- M )来保存这个图,把第 0 列和第M + 1都初始化为1,代

表最右边最左边刚开始就是不能走的，为最左边开辟一个节点为 0 ,为最右边开辟一个节点为N * M +１,图中下标为(i, j)的节点以编号 (i - 1)

* M + j代表，也就是图中的点编号从左到右，坐上到下分别为1,2,3,4,5,6.......N * M,如果(i, j)周围八个方向有一个节点的值为 1 那么就可

以把这俩个节点并到一个集合里面，在并的同时查询 0 号节点和 N * M +１号节点是否在一个集合里面，那就说明左右被黑色的联通,上下被彻

底断绝联系.

代码：

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #include <iostream>  
 4 using namespace std;  
 5   
 6 const int MAXN = 500;  
 7 int pre[MAXN * MAXN + 7];  
 8 int Gra[MAXN + 7][MAXN + 7];  
 9 //上下左右以及斜着的八个方向
10 int dirX[] = {-1, -1, -1,  0, 0,  1, 1, 1};  
11 int dirY[] = {-1,  0,  1, -1, 1, -1, 0, 1};  
12 int n, m;  
13 //初始化并查集数组
14 void initPre()  
15 {  
16     for(int i  = 0; i <= n * m + 1; i++)  
17         pre[i] = i;  
18 }  
19 //初始化存放图的数组
20 void initGra()  
21 {  
22     memset(Gra, -1, sizeof(Gra));  
23     for(int i = 1; i <= n; i++)//×î×ó±ßºÍ×îÓÒ±ßÒ»¿ªÊ¼¾ÍÊÇ²»Á¬Í¨µÄ  
24         Gra[i][0] = Gra[i][m + 1] =  1;  
25 }  
26 
27 //带压缩路径的查找操作
28 int Find(int x)  
29 {  
30     return x == pre[x] ? x : pre[x] = Find(pre[x]);  
31 }  
32 
33 void mix(int x, int y)  
34 {  
35     int fx = Find(x);  
36     int fy = Find(y);  
37     if(fx > fy) pre[fx] = fy;  
38     if(fx < fy) pre[fy] = fx;  
39 }  
40 
41 //把(i,j)点和其八个方向的不能走的地方并到一个集合里面
42 void deal(int i, int j)  
43 {  
44     for(int s = 0; s < 8; s++)  
45     {  
46         int x = i + dirX[s];  
47         int y = j + dirY[s];  
48         if(Gra[x][y] == 1)  
49         {  
50             if(y == 0)          mix(0, (i - 1) * m + j);//最左边
51             else if(y == m + 1) mix(n * m + 1, (i - 1) * m + j);//最右边  
52             else                mix((x - 1) * m + y, (i - 1) * m + j);  
53         }  
54     }  
55 }  
56   
57 int main()  
58 {  
59     //freopen("in.txt", "r", stdin);  
60     int T;  
61     scanf("%d",&T);  
62     while(T--)  
63     {  
64         scanf("%d%d",&n, &m);  
65         initPre();  
66         initGra();  
67         for(int i = 1; i <= n; i++ ){  
68             for(int j = 1; j <= m; j++)  
69             {  
70                 scanf("%1d",&Gra[i][j]);  
71                 if(Gra[i][j] == 1)  
72                     deal(i , j);      
73             }  
74         }  
75         int Q;  
76         scanf("%d",&Q);  
77         int flag = 0;//是否彻底断绝  
78         int ans = -1;  
79         if(Find(0) == Find(n * m + 1)){ans = 0; flag = 1; }  
80         for(int i = 1; i <= Q; i++)  
81         {  
82             int x, y;  
83             scanf("%d%d",&x, &y);  
84             Gra[x + 1][y + 1] = 1;  
85             deal(x + 1, y + 1);  
86             if( !flag && Find(0) == Find(n * m + 1)){//如果代表最左边的节点和代表最右边的节点在一个集合里面，说明左右联通了，上下断绝了
87                 ans = i;  
88                 flag = 1;  
89             }      
90         }  
91         printf("%d
",ans);  
92     }  
93     return 0;  
94 }