[搜索][最短路徑]BYVoid魔獸世界模擬題Stage.1 埃雷薩拉斯的尋寶 eldrethalas 解題報告

【問題描述】

一萬兩千年前，精靈還是在艾薩拉女王的統治下，辛德拉是女王手 下一名很有地位的法師。他受任建造了一座城市，來保存女王的法師們進行魔法研究的成果和法術物品。這個城市就是埃雷薩拉斯。永恆之井的爆炸，使這裏的精靈 和總部聯繫中斷，並失去了永恆之井的水做爲能量的來源。辛德拉的後人爲了滿足魔法的慾望，捕獵了一個惡魔，伊莫塔爾，並以水晶塔建造了一個帶有能量平衡係 統的結界監獄，水晶塔從惡魔身上吸取能量，一部分維持結界監獄，一部分可以讓精靈狂熱者吸收。近萬年平安無事。但是現在，惡魔的能量被消耗得越來越多，最 終變得不穩定，已經難以維持結界監獄的消耗。統治這裏的托爾塞林王子開始下令屠殺。只有少數狂熱者之外的其他人都要死，以減少魔法能量的消耗。

終於，強大的戈多克食人魔入侵了埃雷薩拉斯，並殺死了大量的精靈。他們把這裏當作他們的領地，叫做厄運之槌。面臨滅頂之災的精靈們把他們祖先留下的寶藏用魔法結界藏了起來，以防戈多克食人魔搶走。

作爲一名勇敢的探險者，你悄悄來到了埃雷薩拉斯，來尋找傳說中的寶藏。終於，你看到了寶藏，他就在你的前方不遠處。但是你不能貿然前進，因爲路上有着強大的魔法結界。這些結界根據能量的不同分爲P種，踏入每種結界，你都會受到一定的傷害。爲了拿到寶藏，這些傷害算不了什麼。但是你要儘可能地減少傷害，請你設計一條路綫，使你穿越結界獲取寶藏受到的傷害最少。

下面是一個魔法結界能量示意圖，結界是一個正方形，內部有P種不同的能量，每種字母表示一種能量。你從最上端開始走，每次能走到與你所在的位置鄰接的一個單元格，或者在同種能量結界中任意傳送。重複進入同一種能量結界不會再次受到傷害。

|AAABBC|

|ABCCCC|

|AABBDD|

|EEEEEF|

|EGGEFF|

|GGFFFF|

你有H點生命值，請你在貿然行動之前先判斷是否能夠活着（生命值大於0）穿越結界拿到寶藏，如果能夠，請求出最大的生命值。

輸入格式

第1行 三個非負整數 N P H。N爲結界的邊長，P爲不同的能量結界的數量，H爲你的生命值。

第2-P+1行 每行一個非負整數，表示走到該種能量結界受到的傷害值。

第P+2至第P+2+N行 每行N個正整數，爲地圖上該單元格的能量種類的編號，編號爲1..P。

輸出格式

如果你能夠穿越結界到達對岸的寶藏，輸出最多剩餘的生命值。如果不能穿越，輸出NO。

樣例輸入

6 7 10

3

1

2

2

1

1

3

1 1 1 2 2 3

1 2 3 3 3 3

1 1 2 2 4 4

5 5 5 5 5 6

5 7 7 5 6 6

7 7 6 6 6 6

樣例輸出

7

樣例說明

路綫爲

起始-2-5-6-目標

1 1 1 2 2 3

1 2 3 3 3 3

1 1 2 2 4 4

5 5 5 5 5 6

5 7 7 5 6 6

7 7 6 6 6 6

數據規模

對於40%數據

4<=N<=10

對於100%數據

4<=N<=50

1<=P<=N*N

0<=H<=200000000

【分析】
搜索+最短路，把每個結界縮成一個點，通過搜索找出與每個結界相鄰接的結界，就這樣構圖就行了。然後用Dijkstra等O(N^2)算法求最短路即可。
【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=2505;
const int MAX=0x7fffffff;
int Mat[MAXN][MAXN];
int Val[MAXN][MAXN];
int Abut[MAXN]={0};
bool used[MAXN][MAXN];
bool flag[MAXN]={false};
int dist[MAXN];
int Map[62][62];
int step[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int N,P,H,E;
int Magic[62];

void init()
{
    scanf("%d %d %d",&N,&P,&H);
   
    E=P+1;
   
    for (int i=1;i<=P;i++)
        scanf("%d",&Magic[i]);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            scanf("%d",&Map[i][j]);
   
    for (int i=1;i<=P;i++)
        for(int j=1;j<=P;j++)
            used[i][j]=false;
       
    bool used[MAXN];
    memset(used,false,sizeof(used));
    for (int i=1;i<=N;i++)
        used[Map[1][i]]=true;
   
    for (int i=1;i<=P;i++)
    {
        if(used[i])
        {
            Abut[0]++;
            Mat[0][Abut[0]]=i;
            Val[0][Abut[0]]=Magic[i];
        }
    }
   
    memset(used,false,sizeof(used));
    for (int i=1;i<=N;i++)
        used[Map[N][i]]=true;
   
    for (int i=1;i<=P;i++)
    {
        if(used[i])
        {
            Abut[i]++;
            Mat[i][Abut[i]]=E;
            Val[i][Abut[i]]=0;
        }
    }
   
    return;
}

void CreatGraph()
{
    int nx,ny;
    int nc;
    for (int k=1;k<=P;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=N;j++)
            {
                if(Map[i][j]!=k)
                    continue;
                for (int m=0;m<4;m++)
                {
                    nx=i+step[m][0];
                    ny=j+step[m][1];
                    if(nx<1 || nx>N || ny<1 || ny>N)
                        continue;
                    nc=Map[nx][ny];
                    if(nc!=k && !used[k][nc] && nc!=-1)
                    {
                        Abut[k]++;
                        Mat[k][Abut[k]]=nc;
                        Val[k][Abut[k]]=Magic[nc];
                        used[k][nc]=true;
                       
                        Abut[nc]++;
                        Mat[nc][Abut[nc]]=k;
                        Val[nc][Abut[nc]]=Magic[k];
                        used[nc][k]=true;
                    }
                }
                Map[i][j]=-1;
            }
        }
    }
}

void Dijkstra(int S)
{
    for (int i=0;i<=E;i++)
    {
        dist[i]=MAX;
        flag[i]=false;
    }
    for(int i=1;i<=Abut[S];i++)
    {
        dist[Mat[S][i]]=Val[S][i];
    }
    dist[S]=0;
    flag[S]=1;
   
    for(int i=0;i<=E;i++)
    {
        int tmp=MAX;
        int u=S;
        for (int j=0;j<=E;j++)
        {
            if(!flag[j] && dist[j]<tmp)
            {
                u=j;
                tmp=dist[j];
            }
        }
        flag[u]=1;
       
        for (int j=0;j<=Abut[u];j++)
        {
            if(!flag[Mat[u][j]])
            {
                int newdist=dist[u]+Val[u][j];
                if(newdist<dist[Mat[u][j]])
                {
                    dist[Mat[u][j]]=newdist;
                }
            }
        }
    }
}

int main()
{
    freopen("eldrethalas.in","r",stdin);
    freopen("eldrethalas.out","w",stdout);
    init();
    CreatGraph();
    Dijkstra(0);
    int res=dist[E];
    if(res<H)
    {
        res=H-res;
        printf("%d\n",res);
    }
    else
        printf("NO\n");
    return 0;
}

【評測結果】
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	55463 KB	0
2	正确	10	0.091 s	55463 KB	0
3	正确	10	0.000 s	55463 KB	0
4	正确	10	0.000 s	55463 KB	0
5	正确	10	0.001 s	55463 KB	0
6	正确	10	0.001 s	55463 KB	0
7	正确	10	0.019 s	55463 KB	0
8	正确	10	0.065 s	55463 KB	0
9	正确	10	0.080 s	55463 KB	0
10	正确	10	0.080 s	55463 KB	0

运行完成
运行时间 0.338 s
平均内存使用 55463 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

各種字符串Hash函數比較

本文轉載自：http://www.byvoid.com/blog/string-hash-compare/
轉載請註明出處。

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

Hash函数	数据1	数据2	数据3	数据4	数据1得分	数据2得分	数据3得分	数据4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也 是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算 法本质是相似的。
在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。
BYVoid原创，欢迎建议、交流、批评和指正。
附：各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{
 unsigned int hash = 0;
 
 while (*str)
 {
  // equivalent to: hash = 65599*hash + (*str++);
  hash = (*str++) + (hash << 6) + (hash << 16) - hash;
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// RS Hash Function
unsigned int RSHash(char *str)
{
 unsigned int b = 378551;
 unsigned int a = 63689;
 unsigned int hash = 0;
 
 while (*str)
 {
  hash = hash * a + (*str++);
  a *= b;
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// JS Hash Function
unsigned int JSHash(char *str)
{
 unsigned int hash = 1315423911;
 
 while (*str)
 {
  hash ^= ((hash << 5) + (*str++) + (hash >> 2));
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
 unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
 unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt  * 3) / 4);
 unsigned int OneEighth  = (unsigned int)(BitsInUnignedInt / 8);
 unsigned int HighBits   = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
 unsigned int hash    = 0;
 unsigned int test    = 0;
 
 while (*str)
 {
  hash = (hash << OneEighth) + (*str++);
  if ((test = hash & HighBits) != 0)
  {
   hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  }
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// ELF Hash Function
unsigned int ELFHash(char *str)
{
 unsigned int hash = 0;
 unsigned int x = 0;
 
 while (*str)
 {
  hash = (hash << 4) + (*str++);
  if ((x = hash & 0xF0000000L) != 0)
  {
   hash ^= (x >> 24);
   hash &= ~x;
  }
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
 unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
 unsigned int hash = 0;
 
 while (*str)
 {
  hash = hash * seed + (*str++);
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// DJB Hash Function
unsigned int DJBHash(char *str)
{
 unsigned int hash = 5381;
 
 while (*str)
 {
  hash += (hash << 5) + (*str++);
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// AP Hash Function
unsigned int APHash(char *str)
{
 unsigned int hash = 0;
 int i;
 
 for (i=0; *str; i++)
 {
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
  }
 }
 
 return (hash & 0x7FFFFFFF);
}

[動態規劃]BYVoid魔獸世界模擬題 Stage.1 靈魂分流藥劑 soultap 解題報告

【問題描述】

幽暗城皇家鍊金師赫布瑞姆剛剛發明瞭一種用來折磨戰俘的新型藥 劑，這種藥劑被稱爲靈魂分流藥劑。靈魂分流藥劑的妙處在於能夠給戰俘帶來巨大的痛苦，但是卻不會讓戰俘死去。這種藥劑中包含了一些治療的成分，所以即使戰 俘想自盡，也會被救活。用這種求生不得，求死不能的感覺，來對付反對希爾瓦娜斯女王的狂徒們，實在是太美妙了。當然，靈魂分流藥劑要限定在一個用量範圍之 內，過少會達不到效果，而過多會直接殺了戰俘。

最近，我們抓獲了一個來自暴風城的探子，他掌握了我們的許多重要情報。希爾瓦娜斯女王命令你用最痛苦的手段折磨他。你從你的導師，靈魂分流藥劑的發明者——皇家鍊金師赫布瑞姆那裏獲得了N瓶藥劑。每瓶按照藥性的不同裝在M個箱子中。每瓶藥劑都有一個規格：對服用者造成的肉體傷害w，對服用者造成的意志折磨v，所屬的箱子t，和對服用者造成的痛苦值p。

據我們測試，那個暴風城探子的生命值爲A，意志力爲B。你要從每個箱子中最多拿取1瓶藥劑餵給他。注意，餵給他的藥劑造成的總肉體傷害不能超過他的生命值A，否則他會死去，總意志折磨不能超過他的意志力B，否則他會精神崩潰，我們沒有必要給一個精神崩潰的傻瓜製造那麼多痛苦。在不讓他死去或者精神崩潰的前提下，你要儘可能多的給他製造痛苦，你能解決這個問題嗎？

輸入格式

第1行：四個整數N,M,A,B，M個箱子的編號爲1..M。

第2行至第N+1行：第i+1行四個整數w,v,t,p表示第i瓶藥劑的肉體傷害，意志折磨，所屬箱子的編號，和造成的痛苦值。

輸出格式

第1行：一個整數，表示能夠造成的最大的痛苦值。

樣例輸入

5 3 20 20

5 10 1 200

10 5 1 100

8 11 2 56

10 10 2 50

5 5 3 100

樣例輸出

300

數據規模

對於30%的數據

N<=30

M<=5

對於100%的數據

N<=100

M<=10

A,B<=100

【分析】

經典的動態規劃，0/1背包問題。

以每個箱子為階段劃分狀態，而每個箱子又是一個最優子問題。

狀態設定

Box[i].W[j]：第i個箱子中第j件物品的肉體傷害

Box[i].V[j]：第i個箱子中第j件物品的意志折磨

Box[i].P[j]：第i個箱子中第j件物品的傷害值

Box[i].num：第i個箱子中 藥劑的總數

F[k][i][j] ：對於前k個箱子，當探子生命值為i，意志力為j時的最大傷害值

邊界條件：

F[0][i][j]=0

狀態轉移方程：

F[k][i][j]= Max{ Max{F[k-1][i-Box[k].W[m]][j-Box[k].V[m]]+Box[k].P[m]} , F[k-1][i][j] }  (1<=m<=Box[k].num)

目標狀態：

F[M][A][B]

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int F[11][101][101];

class BOX
{
public:
    int num;
    int W[101];
    int V[101];
    int P[101];
    BOX()
    {
        num=0;
    }
}Box[11];
int N,M;
int A,B;


void init()
{
    scanf("%d %d %d %d\n",&N,&M,&A,&B);
    int w,v,t,p;
    for (int i=1;i<=N;i++)
    {
        scanf("%d %d %d %d\n",&w,&v,&t,&p);
        Box[t].num++;
        Box[t].W[Box[t].num]=w;
        Box[t].V[Box[t].num]=v;
        Box[t].P[Box[t].num]=p;
    }
    return;
}

void dynamic()
{
    int tmp;
    for (int i=1;i<=A;i++)
        for (int j=1;j<=B;j++)
                F[0][i][j]=0;
       
    for (int k=1;k<=M;k++)
    {
        for(int i=1;i<=A;i++)
        {
            for (int j=1;j<=B;j++)
            {
                int Max=0;
                for (int m=1;m<=Box[k].num;m++)
                {
                    if(i-Box[k].W[m]>=0 && j-Box[k].V[m]>=0)
                    {
                        tmp=F[k-1][i-Box[k].W[m]][j-Box[k].V[m]]+Box[k].P[m];
                        if(tmp>Max)
                            Max=tmp;
                    }
                }
                if (F[k-1][i][j]>Max)
                    Max=F[k-1][i][j];
                F[k][i][j]=Max;
            }
        }
    }
    printf("%d\n",F[M][A][B]);
}

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

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	724 KB	0
2	正确	10	0.006 s	724 KB	0
3	正确	10	0.001 s	724 KB	0
4	正确	10	0.001 s	724 KB	0
5	正确	10	0.005 s	724 KB	0
6	正确	10	0.006 s	724 KB	0
7	正确	10	0.006 s	724 KB	0
8	正确	10	0.006 s	724 KB	0
9	正确	10	0.006 s	724 KB	0
10	正确	10	0.006 s	724 KB	0

运行完成
运行时间 0.042 s
平均内存使用 724 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[動態規劃]BYVoid魔獸世界模擬題: 艾薩拉的激流 azshara 解題報告

      艾薩拉的激流  azshara
問題描述

沿着卡利姆多北方邊界延展的破碎的海岸，在世界大分裂之前曾經 是暗夜精靈首都艾薩琳的一部分，艾薩拉。惡魔終於從這個世界被消除，這片土地被撕碎並被大海吞沒，剩下的只有曾經雄偉城市的廢墟。自那以後，這個岩石交錯 的島嶼、峭壁懸崖和珊瑚叢生的海洋成爲許多傳說來源。暗夜精靈們認爲這是個被詛咒的地方，從來沒有人敢來探險，連經驗最豐富的船長都從這裏繞行。因爲這裏 有巨大的水生物，可怕的暗礁，強大的激流與巨浪。然而傳聞這裏水下有着驚人的寶藏，一直吸引着地精們。

地精菲利克斯購買了最好的探險艇，來探索艾薩拉海岸水下傳說中的寶藏。不出所料，海底果然有大量的寶藏。但是這些寶藏被一個激流覆蓋，菲利克斯不可能把他的探險艇停下來。這個激流可以被描述爲一個W×L的矩形，分成個一個個單元格。每個單元格可能是寶藏，也可能是一塊礁石。從上遊開始，每過1秒， 菲利克斯的探險艇就會被衝往下游的一個單位。在被衝往下游的過程中，菲利克斯可以控制方向，選擇他的正前，左邊，或右邊的一個單位，以免觸碰礁石。菲利克 斯從這個激流的最上游的任意一個單元格開始向下漂流，每經過一個單元格就可以取走這個單元格上的寶藏。菲利克斯千萬不能碰到礁石，否則他的探險艇會損壞。 請你算出，菲利克斯最多一共能拿到多少個單位的寶藏。

輸入格式

第一行，兩個整數W，L。

接下來的L行，每行W個整數，以”從上游到下游，面朝水流方向從左向右“的順序依次爲每個單元格中的寶藏的單位數目，如果爲-1則表示這個單元格是礁石。

輸出格式

一個整數，表示得到的寶藏。

數據規模

1<=W<=1000

1<=L<=10000

所有涉及到的數字不會超過32位帶符號整型的範圍

樣例輸入

3 5

5 1 3

-1 7 -1

5 1 10

4 -1 7

20 10 5

樣例輸出

41

樣例說明

上游->下游	1	2	3	4	5
1	5	-1	5	4	20
2	1	7	1	-1	10
3	3	-1	10	7	5

如上表，菲利克斯可以從(1,1)開始，第1秒向右轉一下，被衝到(2,2)。第2秒向左轉一下，被衝到(3,1)。接下來正前行走，經過(4,1),(5,1)，一共拿到5+7+5+4+20=41個單位的寶藏。

本文由BYVoid大牛開發的開源的中文轉換引擎——Opencc翻譯。

(話說 我用BYVoid開發的翻譯引擎 翻譯BYVoid出的題目。。大牛啊！)

【分析】

簡單的動態規劃題目。

用mat[i][j]表示讀入的那個矩陣。

mat[i][j]=Max{mat[i-1][j-1],mat[i][j-1],mat[i+1][j-1]}+mat[i][j]

目標狀態：

   Max{mat[i][L]}

注意-1的判斷即可。

【我的代碼】

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define Max(a,b) a>=b?a:b;
using namespace std;

int W,L;
int mat[1002][10002];
int M=0;

void init()
{
    scanf("%d %d\n",&W,&L);
    for (int i=1;i<=L;i++)
        for (int j=1;j<=W;j++)
            scanf("%d",&mat[j][i]);
}

void print()
{
    for (int i=1;i<=W;i++)
    {
        for (int j=1;j<=L;j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

void dp()
{
    int tmp;
    for (int i=2;i<=L;i++)
    {
        for (int j=1;j<=W;j++)
        {
            if(mat[j][i]==-1)
                continue;
            tmp=0;
            if(j-1>=1 && mat[j-1][i-1]!=-1)
                tmp=Max(tmp,mat[j-1][i-1]);
           
            if(mat[j][i-1]!=-1)
                tmp=Max(tmp,mat[j][i-1]);
           
            if(j+1<=W && mat[j+1][i-1]!=-1)
                tmp=Max(tmp,mat[j+1][i-1]);
            mat[j][i]+=tmp;
            //if(mat[j][i]>M)
                //M=mat[j][i];
        }
    }
}

int main()
{
    freopen("azshara.in","r",stdin);
    freopen("azshara.out","w",stdout);
    init();
//    print();
    dp();
    //print();
    //int M=0;
    for (int i=1;i<=W;i++) 
        M=Max(M,mat[i][L]); 
    cout<<M<<endl;
    return 0;
}

【測評結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	39421 KB	0
2	正确	10	0.579 s	39421 KB	0
3	正确	10	0.000 s	39421 KB	0
4	正确	10	0.000 s	39421 KB	0
5	正确	10	0.014 s	39421 KB	0
6	正确	10	0.572 s	39421 KB	0
7	正确	10	0.572 s	39421 KB	0
8	正确	10	0.570 s	39421 KB	0
9	正确	10	0.567 s	39421 KB	0
10	正确	10	0.573 s	39421 KB	0

运行完成
运行时间 3.447 s
平均内存使用 39421 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[廣度優先搜索]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;
}