特别经典的一个题，还有一种方法就是二分+bfs
题意：空间内n*m个点，每个点是0或者1，0代表此点可以走，1代表不能走。接着经过q年，每年一个坐标表示此点不能走。问哪年开始图上不能出现最上边不能到达最下边的情况了
图上连通性可以使用并查集判断，但是并查集不善于删边，却善于添边。所以我们倒着来想就是离线倒序添边（横向并查，再纵向并查），当某次判断时图已经连通，就结束。
我使用二维并查集，其实就是使用结构体代替一维数组。接着就是每次一定要从x轴小的点到达x轴大的点，最后注意添边时，我们需要此点向四个方向判断添边
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=510; struct node { int xx,yy; } fat[Max][Max]; //二维并查集 int xx1[Max*Max],yy1[Max*Max]; char str[Max][Max]; int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}; //四个方向 void Init(int n,int m) { for(int i=0; i<n; ++i) { for(int j=0; j<m; ++j) { fat[i][j].xx=i; fat[i][j].yy=j; } } return ; } node Find(int x,int y) { if(x==fat[x][y].xx&&y==fat[x][y].yy) return fat[x][y]; return fat[x][y]=Find(fat[x][y].xx,fat[x][y].yy); } int Union(int xx1,int yy1,int xx2,int yy2)//合并两个二维并查集 { //printf("%d %d %d %d ",xx1,yy1,xx2,yy2); node xy1=Find(xx1,yy1); node xy2=Find(xx2,yy2); if(xy1.xx==xy2.xx&&xy1.yy==xy2.yy) return 0; if(xy1.xx<xy2.xx)//保证向下就好 fat[xy1.xx][xy1.yy]=xy2; else fat[xy2.xx][xy2.yy]=xy1; return 1; } int Jud(int n,int m)//判断是否连通 { for(int i=0; i<m; ++i) { node xy1=Find(0,i);//第一行可以到达的最下方位置 if(xy1.xx==n-1) return 1; } return 0; } int Solve(int n,int m,int q) { for(int i=0; i<n; ++i) { for(int j=0; j<m-1; ++j) { if(str[i][j]=='0'&&str[i][j+1]=='0') { int ans=Union(i,j,i,j+1);//横向合并 //printf("%d ",ans); } } } for(int j=0; j<m; ++j) { for(int i=0; i<n-1; ++i) { if(str[i][j]=='0'&&str[i+1][j]=='0') { int ans=Union(i,j,i+1,j);//纵向合并 //printf("ver=%d ",ans); } } } if(Jud(n,m)) return -1; int p; for(int i=q-1; i>=0; --i) { p=0; str[xx1[i]][yy1[i]]='0'; while(p<4) { if(xx1[i]+dir[p][0]>=0&&xx1[i]+dir[p][0]<n&&yy1[i]+dir[p][1]>=0&&yy1[i]+dir[p][1]<m&&str[xx1[i]+dir[p][0]][yy1[i]+dir[p][1]]=='0')//需要连接四个方向可行的地方 Union(xx1[i],yy1[i],xx1[i]+dir[p][0],yy1[i]+dir[p][1]); p++; } if(Jud(n,m)) return i+1; } return 0; } int main() { int t,n,m,q; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); Init(n,m); for(int i=0; i<n; ++i) scanf("%s",str[i]); scanf("%d",&q); for(int i=0; i<q; ++i) //存下来，倒着增加边 { scanf("%d %d",&xx1[i],&yy1[i]); str[xx1[i]][yy1[i]]='1'; } printf("%d ",Solve(n,m,q)); } return 0; }