题目大意：给你一个地图0代表可以通过1代表不可以通过。只要能从第一行走到最后一行，那么中国与印度是可以联通的。现在给你q个点，每年风沙会按顺序侵蚀这个点，使改点不可通过。问几年后中国与印度不连通。若一直联通输出-1.
题目思路：看数据这道题就是卡时间的，我们的基本思路是每当风沙侵蚀一个点，我们就进行一次广搜，看看图上下是否联通，我们应尽可能的去优化这个过程。
所以我们可以在遍历年的时候用二分查找：
若当年图可以上下联通,则继续向右查找
若当年图上下无法联通，则向左查找
剪枝：
为了省时间我们应该剪去一些不必要走的路径：假设第一行的x点在第n年已经不可达到最后一行，那么我们就标记一下，在m（m>n）年时，不对x点经行广搜。
具体看代码：
#include<cstdio> #include<stdio.h> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f3f #define MAX 1000005 #define mod 1000000007 using namespace std; struct node { int x,y; }; char Map[505][505]; int vis[505][505],n,m,q,a[MAX],b[MAX],book[MAX],v[4][2]= {{1,0},{-1,0},{0,1},{0,-1}},Stack[MAX]; int check(int x,int y) { if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && Map[x][y]=='0') return 1; return 0; } int BFS(int x,int y) { vis[x][y]=1; node now,next; now.x=x; now.y=y; queue<node>Q; Q.push(now); while(!Q.empty()) { now=Q.front(); Q.pop(); if(now.x==n-1) { return 1; } for(int i=0; i<4; i++) { next.x=now.x+v[i][0]; next.y=now.y+v[i][1]; if(check(next.x,next.y)) { vis[next.x][next.y]=1; Q.push(next); } } } return 0; } int main() { int T,i,j,ans,ok1,ok2,ok,L,R,top; scanf("%d",&T); while(T--) { ok1=0;//记录第一行是否有可行点 ok2=0;//记录第二行是否有可行点 ok=0; scanf("%d%d",&n,&m); for(i=0; i<n; i++) scanf("%s",Map[i]); scanf("%d",&q); for(i=1; i<=q; i++) scanf("%d%d",&a[i],&b[i]); for(i=0; i<m; i++) { if(Map[0][i]=='0') ok1=1; if(Map[n-1][i]=='0') ok2=1; } if(ok1 && ok2) ok=1; if(!ok)//若第一行或最后一行无可行点，直接输出0 { printf("0 "); continue; } ans=0; L=1; R=q; memset(book,0,sizeof(book));//记录第一行被剪去的点 while(R>L)//二分查找年份 { top=0; int mid=L+(R-L)/2; for(i=1; i<=mid; i++)//当前为mid年，更新地图被侵蚀的点 { int x=a[i]; int y=b[i]; Map[x][y]='1'; } ok=0; for(i=0; i<m; i++) { if(Map[0][i]=='0' && !book[i]) { memset(vis,0,sizeof(vis)); ok=BFS(0,i); if(ok)//当年图上下可连通 break; else { Stack[++top]=i;//若该点无法到达最后一行，记录改点为可能要被剪去的点 } } } if(ok) { L=mid+1; ans=max(ans,mid); for(j=1; j<=top; j++)//剪枝 { int num=Stack[j]; book[num]=1; } top=0; } else { R=mid; } for(i=1; i<=mid; i++)//还原地图 { int x=a[i]; int y=b[i]; Map[x][y]='0'; } } ok=0; for(i=1; i<=L; i++) { int x=a[i]; int y=b[i]; Map[x][y]='1'; } for(i=0; i<m; i++) { if(Map[0][i]=='0' && !book[i]) { memset(vis,0,sizeof(vis)); ok=BFS(0,i); if(ok) break; else { Stack[++top]=i; } } } if(ok) ans=L; if(ans == q) ans=-1; else ans++; printf("%d ",ans); } return 0; }