题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5652
题意：
输入T，接下来T个样例，每个样例输入n，m代表图的大小，接下来n行，每行m个数，代表图，0表示这个位置可以走，1表示走不了，接下来q个点的位置，表示第q个时间这个点的值变成1，就不能走了，问在什么时间开始从最上面无法走到最下面。
最后还是看了别人博客（不争气啊），用并查集的思路就是先给每个点编号，然后用两个数组pre1，pre2数组方便存储编号为i的点所在的点集（并查集）里面最左和最右的值，当最左的值为0，最右的值为m-1是说明这个连续的点集已经把上下隔断了。只是大致说了下，看代码，有人也用了二分+BFS，对q个时间段进行二分，用BFS判断上下是否被隔断，应该是这样，没用这种方法写。
代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 505 int n,m,k,t,ans,id; char str[maxn][maxn]; int num[maxn][maxn];//记录点str[i][j]对应的编号 int pre1[maxn*maxn],pre2[maxn*maxn];//两个数组记录祖先，祖先编号对m取模得出的值就是左右两边最值 int dir[8][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};//八个方向 int find1(int a) { if(a==pre1[a]) return a; return pre1[a]=find1(pre1[a]); } void combine1(int x,int y) { int a=find1(x); int b=find1(y); if(a%m<b%m)//祖先编号对m取模值较小的为合并之后的祖先 pre1[b]=a; else pre1[a]=b; } int find2(int a) { if(a==pre2[a]) return a; return pre2[a]=find2(pre2[a]); } void combine2(int x,int y) { int a=find2(x); int b=find2(y); if(a%m>b%m)//祖先编号对m取模值较大的为合并之后的祖先 pre2[b]=a; else pre2[a]=b; } void bianhao() { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { num[i][j]=++id;//给每个点编号 pre1[id]=id; pre2[id]=id; } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(str[i][j]=='1') { for(int k=0;k<8;k++)//搜索每个黑块周围 { int a=i+dir[k][0]; int b=j+dir[k][1]; if(a>=0&&a<n&&b>=0&&b<m&&str[a][b]=='1') { combine1(num[i][j],num[a][b]); combine2(num[i][j],num[a][b]); } } } } } } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); ans=-1; id=-1; for(int i=0;i<n;i++) scanf("%s",str[i]); bianhao(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { int a=find1(num[i][j]); int b=find2(num[i][j]); if(a%m==0&&b%m==m-1)//在山峰升起前可能两国可能已经隔断 { ans=0; break; } } if(ans!=-1) break; } int q; scanf("%d",&q); for(int s=1;s<=q;s++) { int x,y; scanf("%d%d",&x,&y); str[x][y]='1';//山峰升起 if(ans!=-1) continue; for(int i=0;i<8;i++) { int a=x+dir[i][0]; int b=y+dir[i][1]; if(a>=0&&a<n&&b>=0&&b<m&&str[a][b]=='1') { combine1(num[x][y],num[a][b]); combine2(num[x][y],num[a][b]); int l=find1(num[x][y]); int r=find2(num[x][y]); if(l%m==0&&r%m==m-1)//黑色块所在点集的左右两最值达到左右边界 { ans=s; break; } } } } printf("%d ",ans); } return 0; }