2. 白令海峡
题目ID：9691必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述
很久很久以前，一座大陆桥横跨西伯利亚东端与美洲大陆西端。
处于进化早期的人类，正以部落的形式在大陆上游荡、捕猎，四海为家。在饥饿与寒冷折磨下，人们不断迁徙。在不知不觉中，也许有一支队伍、也许有许多支队伍，跨过了大陆桥，来到了美洲大陆。人类繁衍与进化的脚步自此迈上了美洲大陆。
然而，板块位移，地质变迁，陆地慢慢被大海淹没，广阔的海峡将亚欧大陆和美洲大陆的人类分隔开来。也许是万年，也许是十万年，两岸的人类才能再度相见。
大陆架可以看作一个 𝑛×𝑚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≤𝑇≤10，1≤𝑛,𝑚≤500，1≤𝑞≤𝑛×𝑚，0≤𝑥<𝑛，0≤𝑦<𝑚。
#include<bits/stdc++.h>
using namespace std;
const int M=600;
const int MX=600*600;
int n,m,x[MX],q,y[MX],last=0,dx[4]={0,0-1,1},dy[4]={-1,1,0,0};
char a[M][M];
bool vis[M][M];
void fun(int mid){
if(last<mid){
for(int i=last+1;i<=mid;i++)a[x[i]][y[i]]='1';
}else{
for(int i=mid+1;i<=last;i++)a[x[i]][y[i]]='0';
}
last=mid;
}
bool dfs(int x,int y){
if(x==n)return true;
vis[x][y]=true;
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx<1||tx>n||ty>m||ty<1||vis[tx][ty]||a[tx][ty]=='1')continue;
if(dfs(tx,ty))return true;
}
return false;
}
bool check(int mid){
fun(mid);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)vis[i][j]=false;
}
for(int j=1;j<=m;j++){
if(a[1][j]=='0'&&!vis[1][j]){
if(dfs(1,j))return true;
}
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
last=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cin>>a[i][j];
}
cin>>q;
for(int i=1;i<=q;i++){
cin>>x[i]>>y[i];
x[i]++;
y[i]++;
}
if(check(q)){
cout<<-1<<endl;
continue;
}
int l=0,r=q;
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l+1<<endl;
}
return 0;
}
样例输出1