#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,a[1005][1005],t;
const int d[][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{int x,y;};
queue<node>qu;
bool vis[1005][1005];
bool bfs(int x,int sx,int sy){
if((a[sx][sy]!=0&&a[sx][sy]>=-x)||a[sx][sy]==1) return 0;
vis[sx][sy]=1;
qu.push({sx,sy});
while(!qu.empty()){
node now=qu.front();
qu.pop();
for(int i=0;i<4;i++){
int xx=now.x+d[i][0],yy=now.y+d[i][1];
if(!vis[xx][yy]&&(a[xx][yy]==0||a[xx][yy]<-x)&&1<=xx&&xx<=n&&1<=yy&&yy<=m){
qu.push({xx,yy});
vis[xx][yy]=1;
if(xx==n){
while(!qu.empty()) qu.pop();
return 1;
}
}
}
}
return 0;
}
bool check(int x){
for(int i=1;i<=m;i++){
memset(vis,0,sizeof vis);
bool b=bfs(x,1,i);
if(b) return 1;
}
return 0;
}
signed main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
a[i][j]=ch-'0';
}
}
cin>>q;
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
x++,y++;
a[x][y]=-i;
}
int l=0,r=q;
while(l<r){
int mid=(l+r)/2;
if(!check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<"\n";
}
return 0;
}
已 AC，管理关帖