题目链接：
Mean：
很久以前，中国和印度之间并没有喜马拉雅山相隔，两国的文化交流很频繁。随着喜马拉雅山海拔逐渐增加，两个地区的交流也越来越少，最终没有了来往。
假设当时的地形和我画的一样，蓝色部分代表海洋，而且当时人们还没有发明轮船。黄色部分代表沙漠，而且沙漠上经常有野鬼散步，所以人们不敢到沙漠中行走。 黑色的格子表示山峰，这些山峰都无比高大，所以人无法穿过。白色格子代表平原， 人可以在平原上自由行走。人每次可以向相邻的四个格子走动。此外，我们的考古学家发现还有一些山峰会逐渐形成，通过研究发现，位置在 (x, y)（保证该位置之前没有山峰）的地方在 i 年后出现了山峰。 现在给你若干个位置出现山峰的时间， 你可以计算出中国和印度之间的联系最早被彻底切断的时间吗？
输入描述
多组测试数据, 第一行为组数T(T≤10)。每组测试数据第一行包含两个数 N, M (1≤N,M≤500), 表示地图的大小。接下来 N 行长度为 M 的 0101 字符串。0代表白色格子，1代表山峰。接下来有 Q(1≤Q≤N×M) 行， 第 i(1≤i≤Q) 两个整数 (x,y),0≤x
输出描述
对于每组测试数据，输出一个数, 表示两国最早失联的时间。如果最终两国之间还有联系则输出 -1。
analyse: 二分+bfs; 可以二分所有的时间，找到第一个让上下不连通的那个时间点即可；
#include#include #include #include #include #include #include using namespace std;typedef long long LL;const int maxn=509;const int INF=0x3f3f3f3f;const int mod=2009;char str[maxn][maxn];///原地图char maps[maxn][maxn];///即将修改的地图int vis[maxn][maxn];int n, m;int dir[4][2]= { { 0,1},{ 1,0},{ 0,-1},{-1,0}};struct node{ int x, y;} s[maxn*maxn];///要注意了int BFS(int x, int y){ node p, now, next; p.x = x; p.y = y; queue Q; Q.push(p); memset(vis, 0, sizeof(vis)); vis[0][y] = 1; while(Q.size()) { now = Q.front(); Q.pop(); if(now.x == n-1) return 1; for(int i=0; i<4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0 && next.x =0 && next.y