题目描述
巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。
军团是一个N行M列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。
输入
第1行：四个整数N，M，A，B，表示军团矩阵有N行M列。有A个感染源，B为血色敢死队中领主的数量。
接下来A行：每行有两个整数x，y，表示感染源在第x行第y列。
接下来B行：每行有两个整数x，y，表示领主的位置在第x行第y列。
输出
第1至B行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为0。
样例输入
5 4 2 3 1 1 5 4 3 3 5 3 2 4
样例输出
3 1 3
提示
如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。
【数据规模】
10%数据：N,M<=10
40%数据：N,M<=100
100%数据：1<=M,N<=500，1<=A,B<=M*N
广搜的模板题
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 int n,m,i,j,a,b,head=0,tail=1,t[501][501],visit[501][501]; int mov[4][2]={{0,1},{1,0},{-1,0},{0,-1}};///四个方向 int lz[maxn][2]; struct node { int x,y; }que[250001]; ///首先将每个感染源进入队列,再将每个感染源相邻的进入队列 ///就可得每个单位与感染源的距离,从而得到时间. void bfs(){ while(head<tail){ head++; for(i=0;i<4;i++){///四个方向 int tempx=que[head].x+mov[i][0],tempy=que[head].y+mov[i][1]; if(tempx>0&&tempy>0&&tempx<=n&&tempy<=m&&visit[tempx][tempy]!=1){ tail++;///在范围内并且没有感染过 que[tail].x=tempx;que[tail].y=tempy; visit[tempx][tempy]=1;///被感染 t[tempx][tempy]=t[que[head].x][que[head].y]+1;///时间加1 } } } } int main(){ n=read,m=read,a=read,b=read; for(i=1;i<=a;i++){ que[tail].x=read,que[tail].y=read; visit[que[tail].x][que[tail].y]=1;///被感染 tail++; } /** void bfs(){//标准广搜 int x,y,head=tot,tail=0; while(tail<head){ tail++; x=q[tail][0],y=q[tail][1]; v[x][y]=1; for(int i=0;i<4;i++){ int x1=x+fx[i][0],y1=y+fx[i][1]; if(x1<1||y1<1||x1>n||y1>m) continue;//如果超出边界，跳出 if(v[x1][y1]) continue;//如果已经被感染，跳出 v[x1][y1]=1;//标记被感染 ma[x1][y1]=ma[x][y]+1;//被感染者的感染时间 = 感染者的感染时间 + 1 q[++head][0]=x1,q[head][1]=y1; } } } **/ bfs(); for(i=1;i<=b;i++) lz[i][0]=read,lz[i][1]=read; for(i=1;i<=b;i++) printf("%d\n",t[lz[i][0]][lz[i][1]]); return 0; }
