一一个简简单单的搜索
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int a,b;
int gx[250001],gy[250001];
int lx[250001],ly[250001];
int ti[5001][5000];
int vis[501][501];
int mx[4]={0,0,1,-1};
int my[4]={1,-1,0,0};
struct pa{
int x;
int y;
int ti;
}xx;
queue <pa> q;
int main(){
memset(ti,0x3f,sizeof(ti));
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=a;++i){
scanf("%d%d",&gx[i],&gy[i]);
ti[gx[i]][gy[i]]=0;
q.push((pa){gx[i],gy[i],0});
}
for(int i=1;i<=b;++i){
scanf("%d%d",&lx[i],&ly[i]);
}
while(!q.empty()){
xx=q.front();
q.pop();
if(xx.x<1||xx.x>n||xx.y<1||xx.y>m)
continue;
ti[xx.x][xx.y]=min(ti[xx.x][xx.y],xx.ti);
if(vis[xx.x][xx.y]){
continue;
}
vis[xx.x][xx.y]=1;
for(int i=0;i<=3;++i){
q.push((pa){xx.x+mx[i],xx.y+my[i],xx.ti+1});
}
}
for(int i=1;i<=b;++i){
cout<<ti[lx[i]][ly[i]]<<endl;
}
return 0;
}