题目描述
巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。
军团是一个N行M列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。
输入输出格式
输入格式：
第1行：四个整数N，M，A，B，表示军团矩阵有N行M列。有A个感染源，B为血色敢死队中领主的数量。
接下来A行：每行有两个整数x，y，表示感染源在第x行第y列。
接下来B行：每行有两个整数x，y，表示领主的位置在第x行第y列。
【数据规模】
1<=M,N<=500
1<=A,B<=M*N
输出格式：
第1至B行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为0。
输入输出样例
说明
如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。
1 #include <iostream> 2 #include <cstdio> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <memory.h> 6 7 using namespace std; 8 const int maxn=505,maxt=10000; 9 int time[maxn][maxn],flag[maxn][maxn]; 10 int l,r,source,leader; 11 int dir[5][2]={0,0,-1,0,1,0,0,-1,0,1}; 12 struct node{ 13 int x,y,k; 14 }que[600*600]; 15 16 void bfs(int _l,int _r){ 17 int now=1,tail=2; 18 for(int i=1;i<=l;i++) 19 for(int j=1;j<=r;j++) 20 flag[i][j]=1; 21 flag[_l][_r]=0; 22 que[now].x=_l; 23 que[now].y=_r; 24 que[now].k=0; 25 while(now<=tail){ 26 if(que[now].k<time[que[now].x][que[now].y]){time[que[now].x][que[now].y]=que[now].k; 27 for(int i=1;i<=4;i++){ 28 if(flag[que[now].x+dir[i][0]][que[now].y+dir[i][1]]){ 29 int ll=que[now].x+dir[i][0],rr=que[now].y+dir[i][1]; 30 flag[ll][rr]=0; 31 que[tail].x=ll; 32 que[tail].y=rr; 33 que[tail++].k=que[now].k+1; 34 } 35 }} 36 now++; 37 } 38 } 39 40 int main() 41 { 42 scanf("%d%d%d%d",&l,&r,&source,&leader); 43 for(int i=1;i<=l;i++) 44 for(int j=1;j<=r;j++) 45 time[i][j]=maxt; 46 for(int i=1;i<=source;i++){ 47 int _l,_r; 48 scanf("%d%d",&_l,&_r); 49 bfs(_l,_r); 50 } 51 for(int i=1;i<=leader;i++){ 52 int _l,_r; 53 scanf("%d%d",&_l,&_r); 54 printf("%d ",time[_l][_r]); 55 } 56 return 0; 57 }
刚看完深搜和广搜的教程，想找条题试试水，当时搜的标签是深搜，然后就想都没想按深搜写了……结果爆炸
瞄了眼题解发现是bfs……不过dfs我看教程上要用队列，不敢写，结果看别人的答案发现似乎并不用队列……可以用数组仿照队列实现
但时间上其实还是有点爆炸……一开始写的bfs只是因为在两层循环之间夹了一个变量声明就只能过80分……改到内循环中去以后就过了……很微妙
我觉得肯定还有更快更好的方法，但现在能力不足，再说吧（当然用枚举也有一种办法……很简单，就是分别算最小路径，最小路径当然很容易算出来，但不知道非用bfs如何优化）
再附上dfs爆炸的代码，不舍得就这么扔了，虽然错了但这也是我第一个dfs代码啊
递归果然太暴力了
但也有40分 挺好的
1 #include <iostream> 2 #include <cstdio> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <memory.h> 6 7 using namespace std; 8 const int maxn=5005,maxt=999999; 9 int time[maxn][maxn]; 10 int l,r,source,leader; 11 int dir[5][2]={0,0,-1,0,1,0,0,-1,0,1}; 12 13 void dfs(int _l,int _r){ 14 for(int i=1;i<=4;i++) 15 { 16 int ll=_l+dir[i][0],rr=_r+dir[i][1]; 17 if(time[_l][_r]+1<time[ll][rr]) 18 {time[ll][rr]=time[_l][_r]+1;dfs(ll,rr);} 19 } 20 } 21 22 int main() 23 { 24 scanf("%d%d%d%d",&l,&r,&source,&leader); 25 for(int i=1;i<=l;i++) 26 for(int j=1;j<=r;j++) 27 time[i][j]=maxt; 28 for(int i=1;i<=source;i++){ 29 int _l,_r; 30 scanf("%d%d",&_l,&_r); 31 time[_l][_r]=0; 32 dfs(_l,_r); 33 } 34 for(int i=1;i<=leader;i++){ 35 int _l,_r; 36 scanf("%d%d",&_l,&_r); 37 printf("%d ",time[_l][_r]); 38 } 39 return 0; 40 }