题意：很久之前，在中国和印度之间有通路，通路可以简化为一个n*m的字符串，0表示能通过，1表示障碍，每过一年就有一个坐标变成1，问你什么时候，通路彻底无法通过；
解题思路：无向图的连通性，一般直接搜索或者并查集判定，这里用的是并查集，我们把相连的障碍放到一个集合内，然后如果第一列的某点和最后一列的某点也在这个集合内，那么说明，这个通路被障碍堵死了；
这里要处理下第一列和最后一列的问题，可以选择
#include<iostream>
#include<algorithm>
#define N 605
using namespace std;
int next1[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
int f[N*N];
char a[N][N];
int findf(int x)
{
if(f[x]==x)
return x;
else findf(f[x]);
}
void join(int x,int y)
{
int t1=findf(x);
int t2=findf(y);
if(t1!=t2)
f[t2]=t1;
}
int main()
{
int tx,ty;
int n,m;
int t;
int tt;
cin>>t;
while(t--)
{
cin>>n>>m;
int s,e;
s=n*m;e=s+1;
for(int i=0;i<=e;i++)
f[i]=i;
for(int i=0;i<n;i++)
{
join(s,m*i);join(e,m*i+m-1);
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(a[i][j]=='0')
continue;
for(int k=0;k<8;k++)
{
tx=i+dx[k];ty=j+dy[k];
if(tx<0||ty<0||tx>=n||ty>=m||a[tx][ty]=='0')
continue;
join(i*m+j,tx*m+ty);
}
}
cin>>tt;
int x,y;
int flag=-1;
for(int i=1;i<=tt;i++)
{
cin>>x>>y;
if(flag!=-1)
continue; a[x][y]='1';
for(int k=0;k<8;k++)
{
tx=x+dx[k];ty=y+dy[k];
if(tx<0||ty<0||tx>=n||ty>=m||a[tx][ty]=='0')
continue;
join(tx*m+ty,x*m+y);
}
if(findf(s)==findf(e))
flag=i;
}
cout<<flag<<endl;
}
return 0;
}
添加两点，一点和第一列所有点合并，另一点和最后一列所有点合并，如果这两点在一个集合内了，说明两列内有点在一个集合；