題目描述

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

軍團是一個N行M列的矩陣，每個單元是一個血色先鋒軍的成員。感染瘟疫的人，每過一個小時，就會向四周擴散瘟疫，直到所有人全部感染上瘟疫。你已經(jīng)掌握了感染源的位置，任務是算出血色先鋒軍的領主們感染瘟疫的時間，并且將它報告給巫妖王，以便對血色先鋒軍進行一輪有針對性的圍剿。

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

輸入

第1行：四個整數(shù)N，M，A，B，表示軍團矩陣有N行M列。有A個感染源，B為血色敢死隊中領主的數(shù)量。
接下來A行：每行有兩個整數(shù)x，y，表示感染源在第x行第y列。
接下來B行：每行有兩個整數(shù)x，y，表示領主的位置在第x行第y列。
輸出

第1至B行：每行一個整數(shù)，表示這個領主感染瘟疫的時間，輸出順序與輸入順序一致。如果某個人的位置在感染源，那么他感染瘟疫的時間為0。
輸入樣例

5 4 2 3
1 1
5 4
3 3
5 3
2 4
輸出樣例

3
1
3
說明

數(shù)據(jù)規(guī)模
1<=M,N<=500
1<=A,B<=M*N

.
.
.
.
.
分析
直接bfs

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int gry[300000][3],n1,n,m,a[510][510],m1; bool f[510][510];void bfs(int num) {int head=0,tail=n1;while (head<tail){head++;for (int i=0;i<=3;i++){int x=gry[head][0]+d[i][0];int y=gry[head][1]+d[i][1];if (x>=1&&x<=n&&y>=1&&y<=m&&f[x][y]==false) {tail++;gry[tail][0]=x;gry[tail][1]=y;a[x][y]=gry[tail][2]=gry[head][2]+1; f[x][y]=true; }}} } int main() {scanf("%d%d%d%d",&n,&m,&n1,&m1);memset(f,false,sizeof(f));for (int i=1;i<=n1;i++){int x,y;scanf("%d%d",&x,&y);gry[i][0]=x; gry[i][1]=y;f[x][y]=true;}bfs(n1);for (int i=1;i<=m1;i++){int x,y;scanf("%d%d",&x,&y);printf("%d\n",a[x][y]);} return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/11094924.html

總結(jié)

以上是生活随笔為你收集整理的血色先锋军的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。