白令海峡
题目描述
很久很久以前，一座大陆桥横跨西伯利亚东端与美洲大陆西端。
处于进化早期的人类，正以部落的形式在大陆上游荡、捕猎，四海为家。在饥饿与寒冷折磨下，人们不断迁徙。在不知不觉中，也许有一支队伍、也许有许多支队伍，跨过了大陆桥，来到了美洲大陆。人类繁衍与进化的脚步自此迈上了美洲大陆。
然而，板块位移，地质变迁，陆地慢慢被大海淹没，广阔的海峡将亚欧大陆和美洲大陆的人类分隔开来。也许是万年，也许是十万年，两岸的人类才能再度相见。
大陆架可以看作一个 n×m 的矩形区域，区域内有一些格子已经被海洋所淹没。在接下来的 q 年里，区域内还有一些格子会逐个沉没。那么到底是哪一年两座大陆才会分隔开来呢？
输入格式
第一行一个整数 T 代表数据组数。
每组数据第一行两个整数 n 和 m ，
接下来 n 行每行 m 个整数，为 1 表示已经被淹没，为 0 表示仍为陆地。
接下来一行一个整数 q ，
接下来 q 行每行两个整数，表示沉没的格子坐标。
输出格式
每组数据输出一行，代表答案。如果 q 年之后还连通，输出 -1 。
样例输入
1
4 6
011010
000010
100001
001000
7
0 3
1 5
1 3
0 0
1 2
2 4
2 1
样例输出
4
样例解释
到第 4 年，无法从上面到达下面。
第3年可以从上面走到下面，我们可以想象输入是一个连接着上方和下方的桥。
第0年，我们可以这么走：
数据规模
1≤T≤10，1≤n,m≤500，1≤q≤n×m，0≤x<n，0≤y<m 。
思路
看到这道题，首先我们想到的肯定是搜索，那么是 dfs 还是 bfs 呢？暂时不知道，先往后看。
根据题意， 0 表示没淹没， 1 表示淹没。
如果我们直接暴力，时间复杂度就是 O(nmq)\Rightarrow6.25\times10^{10} ，绝对会
，我们需要时间复杂度更低的方法。
我们设两座大陆用 0 表示不分隔， 1 表示分隔，以这组数据为例：
1
4 6
011010
000010
100001
001000
7
0 3
1 5
1 3
0 0
1 2
2 4
2 1
那么，这个数列就是 \{0,0,0,1,1,1,1\} 。
我们的答案肯定就是这个数列中第一次出现 1 的时间了。
其实这题用的是二分，这样，时间复杂度就是 O(nm\log q) ，可以通过。
我们需要编写一个 bool 类型的函数，如 bool\space check(int\space mid); ，其中， bool 表示能否连通， mid 表示的是第 mid 年的情况。
那么， l 等于多少， r 等于多少呢？答： l=1,r=q 。
然后，搜索的起点和终点又是什么呢？答：起点是所有第 0 行且值为 0 的点，终点是所有第 n-1 行且值为 0 的点。
知道了思路后，这道题就迎刃而解了。