冲刺蓝桥杯-BFS板块（第八天）

多源BFS问题

//多源BFS在开始BFS之前就将两个感染源入队
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int,int> PII;

const int N=510;

int a,b,n,m;
int dist[N][N];
queue<PII> q;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

void bfs(){
while(!q.empty()){
auto t = q.front();
q.pop();

for(int i=0;i<4;i++){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<1||a>n||b<1||b>m)continue;
if(dist[a][b]>=0)continue;

dist[a][b]=dist[t.x][t.y]+1;
q.push({a,b});
}

}
}

int main(){
cin >> n >> m >> a >>b;
memset(dist,-1,sizeof dist);
while(a–){
int x,y;
cin >> x >> y;
q.push({x,y});//bfs之前将起点(感染源)入队
dist[x][y]=0;
}
bfs();

//bfs扫完直接输入领主的位置，直接输出它在第几轮被感染
while(b–){
int x,y;
cin >> x >> y;
cout << dist[x][y] << endl;
}

return 0;
}