2. 白令海峡
题目ID：9691必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述
很久很久以前，一座大陆桥横跨西伯利亚与美洲大陆。
处于进化早期的人类，正以部落的形式在大陆上游荡、捕猎，四海为家。在饥饿与寒冷折磨下，人们不断迁徙。在不知不觉中，也许有一支队伍、也许有许多支队伍，跨过了大陆桥，来到了美洲大陆。人类繁衍与进化的脚步自此迈上了美洲大陆。
然而，板块位移，地质变迁，陆地慢慢被大海淹没，广阔的海峡将亚欧大陆和美洲大陆的人类分隔开来。也许是万年，也许是十万年，两岸的人类才能再度相见。
大陆架可以看作一个 n×mn×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≤101≤T≤10，1≤n,m≤5001≤n,m≤500，1≤q≤n×m1≤q≤n×m，0≤x<n0≤x<n，0≤y<m0≤y<m。
然后呢，我用了二分+bfs
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
int t;
int n,m;
int q;
int a[505][505];
int now[505][505];
int x[250005],y[250005];
void sea(int ii){//第ii年海陆状况
for(int i=1;i<=ii;i++){
now[x[ii]][y[ii]]=1;
}
}
struct box{
int x,y;
};
bool bfs(){
queue<box> que;
que.push({0,0});
bool vis[505][505]={0};
vis[0][0]=1;
while(!que.empty()){
box tp=que.front();
que.pop();
if(tp.x==n+1){
return 1;//联通
}
for(int i=0;i<4;i++){
int nx=tp.x+dx[i];
int ny=tp.y+dy[i];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&now[nx][ny]==0&&!vis[nx][ny]){
vis[nx][ny]=1;
que.push({nx,ny});
}
}
}
return 0;//不连通
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=1;j<=m;j++){
a[i][j]=(int)(s[j-1]-'0');
}
}
cin>>q;
for(int kkkk=1;kkkk<=q;kkkk++){
int xx,yy;
cin>>xx>>yy;
xx++;
yy++;
x[kkkk]=xx;
y[kkkk]=yy;
}
int l=0,r=q+1;
while(l<r){
int mid=(l+r)/2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
now[i][j]=a[i][j];
}
}
sea(mid);
if(bfs()){
l=mid+1;
}
else{
r=mid;
}
}
cout<<l<<endl;
}
return 0;
}
本蒟蒻思路：
把地图数组的最上面一行和最下面一行空出来（都初始化为0，代表两块陆地），然后二分，每次从0,0,搜索到最后一行任意一个位置，如果能搜索到，就是联通，否则不连通，然后加上二分，不知道为啥错了QWQ
