李泽铭
(李泽铭)
1
#include<bits/stdc++.h>
using namespace std;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int n,m,T;
vector<string> g;
vector<pair<int,int>> op;
vector<vector<bool>> flood;
vector<vector<bool>> vis;
bool reachBottom;
void bfs(){
queue<pair<int,int>> q;
for(int i=0;i<n;i++)
fill(vis[i].begin(),vis[i].end(),false);
reachBottom=false;
for(int j=0;j<m;j++){
if(flood[0][j]==false){
vis[0][j]=true;
q.push({0,j});
}
}
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
if(x==n-1){
reachBottom=true;
return;
}
for(int d=0;d<4;d++){
int nx=x+dx[d];
int ny=y+dy[d];
if(nx<0||nx>=n||ny<0||ny>=m){
continue;
}
if(vis[nx][ny]==true||flood[nx][ny]==true){
continue;
}
vis[nx][ny]=true;
q.push({nx,ny});
}
}
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
g.clear();
g.resize(n);
vis.clear();
vis.resize(n,vector<bool>(m));
flood.clear();
flood.resize(n,vector<bool>(m,false));
for(int i=0;i<n;i++)
cin>>g[i];
int q;
cin>>q;
op.clear();
op.resize(q);
for(int i=0;i<q;i++){
int x,y;
cin>>x>>y;
op[i]={x,y};
}
int l=1,r=q;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
for(int i=0;i<n;i++){
fill(flood[i].begin(),flood[i].end(),false);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='1'){
flood[i][j]=true;
}
}
}
for(int i=0;i<mid;i++){
int x=op[i].first;
int y=op[i].second;
flood[x][y]=true;
}
bfs();
if(reachBottom==false){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<ans<<'\n';
}
return 0;
}
