3. 血色先锋队
题目ID：20012必做题100分
最新提交：
Time Limit Exceeded
20 分
历史最高：
Time Limit Exceeded
20 分
时间限制: 1000ms
空间限制: 135536kB
题目描述
巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。
军团是一个 nn 行 mm 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。输入格式
第 11 行：四个整数 nn，mm，aa，bb，表示军团矩阵有 nn 行 mm 列。有 aa 个感染源，bb 为血色敢死队中领主的数量。
接下来 aa 行：每行有两个整数 xx，yy，表示感染源在第 xx 行第 yy 列。
接下来 bb 行：每行有两个整数 xx，yy，表示领主的位置在第 xx 行第 yy 列。
输出格式
第 11 至 bb 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为 00。
样例
Input 1
5 4 2 3 1 1 5 4 3 3 5 3 2 4
Output 1
3 1 3
数据范围
对于 100%100% 的数据，保证 1≤n,m≤5001≤n,m≤500，1≤a,b≤1051≤a,b≤105。
代码：
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
int n,m,aa,b;
struct box{
int x,y,d;
};
int a[505][505];
int go[100005];
bool vis[505][505];
void bfs(int x,int y){//这个感染源到所有领主的距离
queue<box> que;
memset(vis,0,sizeof(vis));
que.push({x,y,0});
vis[x][y]=1;
while(!que.empty()){
box tp=que.front();
que.pop();
if(a[tp.x][tp.y]!=-1&&a[tp.x][tp.y]!=0){
go[a[tp.x][tp.y]]=min(go[a[tp.x][tp.y]],tp.d);
}
for(int i=0;i<4;i++){
int nx=tp.x+dx[i];
int ny=tp.y+dy[i];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0){
vis[nx][ny]=1;
que.push({nx,ny,tp.d+1});
}
}
}
}
void solve(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==-1){
bfs(i,j);
}
}
}
for(int i=1;i<=b;i++){
cout<<go[i]<<" ";
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&aa,&b);
while(aa--){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=-1;//感染源的位置
}
for(int i=1;i<=b;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=i;//领主的位置
}
memset(go,0x3f3f3f3f,sizeof(go));
solve();
return 0;
}
/*
颠倒空格
*/
