血色先锋队
题目背景
巫妖王的天灾军团终于卷土重来,血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团,以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围,现在他们将主力只好聚集了起来,以抵抗天灾军团的围剿。可怕的是,他们之中有人感染上了亡灵瘟疫,如果不设法阻止瘟疫的扩散,很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒,这个叛徒已经投靠了天灾军团,想要将整个血色先锋军全部转化为天灾军团!无需惊讶,你就是那个叛徒。在你的行踪败露之前,要尽快完成巫妖王交给你的任务。
题目描述
军团是一个 $n$ 行 $m$ 列的矩阵,每个单元是一个血色先锋军的成员。感染瘟疫的人,每过一个小时,就会向四周扩散瘟疫,直到所有人全部感染上瘟疫。你已经掌握了感染源的位置,任务是算出血色先锋军的领主们感染瘟疫的时间,并且将它报告给巫妖王,以便对血色先锋军进行一轮有针对性的围剿。
输入格式
第 $1$ 行:四个整数 $n$,$m$,$a$,$b$,表示军团矩阵有 $n$ 行 $m$ 列。有 $a$ 个感染源,$b$ 为血色敢死队中领主的数量。
接下来 $a$ 行:每行有两个整数 $x$,$y$,表示感染源在第 $x$ 行第 $y$ 列。
接下来 $b$ 行:每行有两个整数 $x$,$y$,表示领主的位置在第 $x$ 行第 $y$ 列。
输出格式
第 $1$ 至 $b$ 行:每行一个整数,表示这个领主感染瘟疫的时间,输出顺序与输入顺序一致。如果某个人的位置在感染源,那么他感染瘟疫的时间为 $0$。
样例 #1
样例输入 #1
5 4 2 3
1 1
5 4
3 3
5 3
2 4
样例输出 #1
3
1
3
提示
输入输出样例 1 解释
如下图,标记出了所有人感染瘟疫的时间以及感染源和领主的位置。
数据规模与约定
对于 $100\%$ 的数据,保证 $1\le n,m\le500$,$1\le a,b\le10^5$。
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
int n, m, a, b;
int dist[N][N];
PII q[N * N];
int hh = 0, tt = -1; //队头初始化
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void bfs()
{
while(hh <= tt){ //队列不空才会继续搜索
auto t = q[hh++];
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[++tt] = {a, b};
}
}
}
int main()
{
scanf("%d %d %d %d", &n, &m, &a, &b);
memset(dist, -1, sizeof dist); //初始化
while(a--){ //输入感染源
int x1, y1;
scanf("%d %d", &x1, &y1);
q[++tt] = {x1, y1};
dist[x1][y1] = 0;
}
bfs();
//bfs扫完整个地图后直接输入领主的位置,再输出他是第几轮被感染的
while(b--){
int x1, y1;
scanf("%d %d", &x1, &y1);
printf("%d\n", dist[x1][y1]);
}
return 0;
}