Miku

一一个简简单单的搜索

#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;
}