洛谷链接:https://www.luogu.com.cn/problem/P1332
多次入队,但是入队的时候建议在bfs中入队
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
int n,m,a,b;
int dist[1010][1010];
int st[1010][1010];
int go[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
void bfs()
{
queue<PII>q;
for(int i=1;i<=a;i++)
{
int x,y;
cin>>x>>y;
q.push({x,y});
st[x][y] = 1;
dist[x][y] = 0;
}
while(q.size())
{
PII t = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int tx = t.first+go[i][0];
int ty = t.second+go[i][1];
if(tx<1||ty<1||tx>n||ty>m||st[tx][ty]) continue;
st[tx][ty] = 1;
dist[tx][ty] = min(dist[tx][ty],dist[t.first][t.second]+1);
q.push({tx,ty});
}
}
}
int main()
{
cin>>n>>m>>a>>b;
memset(dist,0x3f3f3f3f,sizeof dist);
bfs();
for(int i=1;i<=b;i++)
{
int x,y;
cin>>x>>y;
cout<<dist[x][y]<<endl;
}
return 0;
}