P1332 血色先鋒隊

題目描述

巫妖王的天災軍團終於卷土重來，血色十字軍組織了一支先鋒軍前往諾森德大陸對抗天災軍團，以及一切沾有亡靈氣息的生物。孤立於聯盟和部落的血色先鋒軍很快就遭到了天災軍團的重重包圍，現在他們將主力只好聚集了起來，以抵抗天災軍團的圍剿。可怕的是，他們之中有人感染上了亡靈瘟疫，如果不設法阻止瘟疫的擴散，很快就會遭到滅頂之災。大領主阿比迪斯已經開始調查瘟疫的源頭。原來是血色先鋒軍的內部出現了叛徒，這個叛徒已經投靠了天災軍團，想要將整個血色先鋒軍全部轉化為天災軍團！無需驚訝，你就是那個叛徒。在你的行蹤敗露之前，要儘快完成巫妖王交給你的任務。

軍團是一個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。

輸入輸出樣例

5 4 2 3
1 1
5 4
3 3
5 3
2 4

3
1
3

說明

如下圖，標記出了所有人感染瘟疫的時間以及感染源和領主的位置。

這個題的數據有毒啊。。

怎麼搜都超時啊。。

看了一下題解，發現這個題解非常凝練

首先優化了vis數組

然後優化了儲存領袖的數組、、

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=1001;
 8 void read(int & n)
 9 {
10     char c='+';int x=0;bool flag=0;
11     while(c<'0'||c>'9')
12     {
13         c=getchar();
14         if(c=='-')flag=1;    
15     }
16     while(c>='0'&&c<='9')
17         x=x*10+c-48,c=getchar();
18     flag==1?n=-x:n=x;
19 
20 }
21 int n,m,gr,pep,x,y;
22 int out[MAXN*100];
23 int map[MAXN][MAXN];
24 struct node
25 {
26     int x,y,step;
27 }now,nxt;
28 int willx[MAXN],willy[MAXN];
29 int xx[7]={-1,+1,0,0};
30 int yy[7]={0,0,-1,+1};
31 int jzx[MAXN*100],jzy[MAXN*100];
32 queue<node>q;
33 void bfs()
34 {
35     while(q.size()!=0)
36     {
37         node p=q.front();
38         q.pop();
39         for(int i=0;i<4;i++)
40         {
41             nxt.x=p.x+xx[i];
42             nxt.y=p.y+yy[i];
43             nxt.step=p.step+1;
44             if(nxt.x>=1&&nxt.y>=1&&nxt.x<=n&&nxt.y<=m)
45             {    
46                 if(map[nxt.x][nxt.y]!=-1)continue;
47                 map[nxt.x][nxt.y]=p.step+1;
48                 q.push(nxt);
49             }
50         }
51     }
52 }
53 int main()
54 {
55     memset(map,-1,sizeof(map));
56     read(n);read(m);read(gr);read(pep);
57     for(int i=1;i<=gr;i++)
58     {
59         read(x);read(y);
60         map[x][y]=0;// 感染源
61         now.x=x;
62         now.y=y;
63         now.step=0;
64         q.push(now);
65     }
66     for(int i=1;i<=pep;i++)
67     {
68         read(x);read(y);
69         jzx[i]=x;
70         jzy[i]=y;
71     }
72         bfs();
73     for(int i=1;i<=pep;i++)
74     {
75         printf("%d\n",map[jzx[i]][jzy[i]]);
76     }
77     return 0;
78 }