[廣度優先搜索]BYVoid魔獸世界模擬賽Stage.1 血色先鋒軍

血色先鋒軍

出題者連結：http://www.byvoid.com/

問題描述

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

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

樣例說明

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

 【命題人的分析】

重溫題意，能夠注意到，瘟疫是以時間爲階段逐步擴張的，而題目又要求輸出某個血色領主最早的感染時間。所以，根據這個特性，自然地想到了寬搜的方法。

首先，將所有感染源加入隊列。然後，進入寬搜過程，將所有的格子搜索完畢，得到的即爲每個格子得最早感染時間。

時間複雜度O(M*N)

另外，還有一種算法：

對於所有的領主，枚舉這個領主到所有感染源的距離，取最小值即可。

時間複雜度O(A*B)

這種方法不能獲得滿分

這是一道簡單題，考察基礎算法。

 
【我的代碼】

/*BYVoid 魔獸世界模擬賽 Stage.1 血色先鋒軍*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAXN=0x7fffffff-2;
//bool used[501][501];
int mat[501][501];
int N,M;
int A,B;
const int step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};

class POINT
{
public:
    int x;
    int y;
};

POINT Bos[250001];
POINT Q[2000000];

void init()
{
    scanf("%d %d %d %d\n",&N,&M,&A,&B);
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
        //    used[i][j]=true;
            mat[i][j]=MAXN;
        }
    }
   
    int a,b;
    for (int i=1;i<=A;i++)
    {
        scanf("%d %d\n",&a,&b);
        mat[a][b]=0;
        //used[a][b]=false;
        Q[i-1].x=a;
        Q[i-1].y=b;
    }
   
    for (int i=1;i<=B;i++)
    {
        scanf("%d %d\n",&a,&b);
        Bos[i].x=a;
        Bos[i].y=b;
    }
    return;
}

void BFS()
{
    int q=A;
    int h=0;
    int Tx,Ty;
    int Nx,Ny;
   
    while(h<q)
    {
        Tx=Q[h].x,Ty=Q[h].y;
        //used[Tx][Ty]=false;
       
        for (int i=1;i<=4;i++)
        {
            Nx=Tx+step[i][0];
            Ny=Ty+step[i][1];
            if(Nx>=1 && Nx<=N && Ny>=1 && Ny<=M)
            {
                if(mat[Tx][Ty]+1<mat[Nx][Ny])
                {
                    mat[Nx][Ny]=mat[Tx][Ty]+1;
                    Q[q].x=Nx,Q[q].y=Ny;
                    q++;
                }
            }
        }
        h++;
    }
   
    for (int i=1;i<=B;i++)
    {
        Tx=Bos[i].x;
        Ty=Bos[i].y;
        cout<<mat[Tx][Ty]<<endl;
    }
   
    return;
}

int main()
{
    freopen("crusade.in","r",stdin);
    freopen("crusade.out","w",stdout);
    init();
    BFS();
    return 0;
}