2018.9.4南海中學(xué)測試T1

**1、柵欄迷宮

田野上搭建了一個(gè)黃金大神專用的柵欄圍成的迷宮。幸運(yùn)的是，在迷宮的邊界上留出了兩段柵欄作為迷宮的出口。更幸運(yùn)的是，所建造的迷宮是一個(gè)“完美的”迷宮：即你能從迷宮中的任意一點(diǎn)找到一條走出迷宮的路。給定迷宮的寬W(1<=W<=38)及長H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面給出的格式表示一個(gè)迷宮。然后計(jì)算從迷宮中最“糟糕”的那一個(gè)點(diǎn)走出迷宮所需的步數(shù)(就是從最“糟糕”的一點(diǎn)，走出迷宮的最少步數(shù)）。（即使從這一點(diǎn)以最優(yōu)的方式走向最靠近的出口，它仍然需要最多的步數(shù)）當(dāng)然了，黃金大神讓你必須只會(huì)水平或垂直地在X或Y軸上移動(dòng)，你不能從來不走對(duì)角線。每移動(dòng)到一個(gè)新的方格算作一步（包括移出迷宮的那一步）這是一個(gè)W=5,H=3的迷宮：

如上圖的例子，柵欄的柱子只出現(xiàn)在奇數(shù)行或奇數(shù)列。每個(gè)迷宮只有兩個(gè)出口。
PROGRAM NAME: maze
INPUT FORMAT: (file maze.in)
第一行： W和H（用空格隔開）
第二行至第2*H+1行：每行2*W+1個(gè)字符表示迷宮
OUTPUT FORMAT: (file maze.out)
輸出一個(gè)單獨(dú)的整數(shù)，表示能保證牛從迷宮中任意一點(diǎn)走出迷宮的最小步數(shù)。
SAMPLE INPUT
5 3

SAMPLE OUTPUT
9

題目很容易看懂，每個(gè)點(diǎn)到最近的出口都有一個(gè)最短路徑，那么就求出所有點(diǎn)走出最近出口的最短路徑的最大值。那么想法很簡單，直接兩個(gè)BFS就ok了。每次BFS保存走到這個(gè)格子的最小值，跑完兩次之后找最大值就可以了。

然后這道題目和其他題目不同的是，它的圖很奇怪，并不是經(jīng)常見到的01圖。觀察這個(gè)圖可得知，其實(shí)W一共有2*W+1這么大， H也只是有2*H+1這么大。然后奇數(shù)行都是墻，都不是能走的格子。還有一個(gè)最重要的問題，這個(gè)圖之中還有空格。這個(gè)讓我們保存這個(gè)圖有一點(diǎn)難度。
所以我就像下面代碼一樣保存這個(gè)圖：

    for(int i=1;i<=h;i++)
    {
        getchar();
        char x; 
        for(int j=1;j<=w;j++)
        {
            x=getchar();
            if(x!=' ')
              m[i][j]=true;
        } 
    }

每次讀入一個(gè)字符，用getchar（）不僅能讀入空格，也能讀入換行符。所以在讀入完每一行的數(shù)據(jù)之后都要getchar()一下。然后就判斷讀入的是否是空格就ok了。

然后就是保存出口的問題了。這道題我一開始爆零就是因?yàn)檎页隹谔媪?，認(rèn)為出口肯定一個(gè)在上下，一個(gè)在右，所以兩次BFS前現(xiàn)在上下找一個(gè)出口，或者在左右找一個(gè)出口。
這樣明顯是錯(cuò)誤的嘛，所以找出口在輸入的時(shí)候加上一條判斷，如果是出口就保存，那就ok啦。

if((i==1)&&(x==' ')) {tail++;dl[tail][0]=i+1;dl[tail][1]=j;}
if((i==h)&&(x==' ')) {tail++;dl[tail][0]=i-1;dl[tail][1]=j;}
if((j==1)&&(x==' ')) {tail++;dl[tail][0]=i;dl[tail][1]=j+1;}
if((j==w)&&(x==' ')) {tail++;dl[tail][0]=i;dl[tail][1]=j-1;}

然后我在我錯(cuò)誤的程序上修改后，測試完有一個(gè)點(diǎn)總是超時(shí)。而且這個(gè)圖也是特別的奇葩。

這個(gè)圖超級(jí)帥，超有規(guī)律，但是我就是超時(shí)了。比這個(gè)數(shù)據(jù)還大的數(shù)據(jù)我都不超時(shí)，就這個(gè)超時(shí)了。然后我調(diào)試的時(shí)候發(fā)現(xiàn)，我在BFS時(shí)死循環(huán)了。然后我看了很久，才發(fā)現(xiàn)我犯了一個(gè)錯(cuò)誤，而且這個(gè)錯(cuò)誤在我寫B(tài)FS時(shí)也是很常見。
大家先看看我錯(cuò)誤的BFS：

void bfs()
{
    memset(vis,false,sizeof(vis));
    while(!q.empty() )
      q.pop() ;
    read_into(a,b);
    ans[a][b]=1;
    while(!q.empty())
    {
        A d=q.front();
        q.pop();
        int x=d.xi,y=d.yi;
        vis[x][y]=true;
        for(int i=0;i<4;i++)
        {
            if(!m[x+DX[i]][y+DY[i]])
            {
                int x_=x+X[i];
                int y_=y+Y[i];
                if(!vis[x_][y_] && ans[x][y]+1<=ans[x_][y_])
                {
                    if(x_>0 && x_<=h && y_>0 && y_<=w)
                    {
                        ans[x_][y_]=min(ans[x_][y_],ans[x][y]+1);
                        read_into(x_,y_);
                    }
                }
            }
        }
    }
}

先解釋一下，能走的格子之間是有墻的，所以先判斷距離為一的地方是否時(shí)墻，如果不是墻表示能走，所以就走兩步，這是由于這道題才這么做的。

回歸正題，那么這個(gè)BFS看上去沒錯(cuò)的，但是導(dǎo)致了死循環(huán)，為什么呢？
看看我vis數(shù)組，標(biāo)記的位置是在當(dāng)執(zhí)行到這個(gè)點(diǎn)的時(shí)候才標(biāo)記為true。那么就會(huì)出現(xiàn)一個(gè)情況，我很多個(gè)點(diǎn)都能重復(fù)走到一個(gè)點(diǎn)，那么我這個(gè)點(diǎn)就一直入隊(duì)，一直入一直入，所以導(dǎo)致了死循環(huán)。
解決辦法很簡單，當(dāng)發(fā)現(xiàn)這個(gè)可以走時(shí)直接標(biāo)記為true，這樣就不會(huì)出現(xiàn)這種重復(fù)入隊(duì)的情況了。

void bfs()
{
    memset(vis,false,sizeof(vis));
    while(!q.empty() )
      q.pop() ;
    read_into(a,b);
    ans[a][b]=1;
    while(!q.empty())
    {
        A d=q.front();
        q.pop();
        int x=d.xi,y=d.yi;

        for(int i=0;i<4;i++)
        {
            if(!m[x+DX[i]][y+DY[i]])
            {
                int x_=x+X[i];
                int y_=y+Y[i];
                if(!vis[x_][y_] && ans[x][y]+1<=ans[x_][y_])
                {
                    if(x_>0 && x_<=h && y_>0 && y_<=w)
                    {
                        ans[x_][y_]=min(ans[x_][y_],ans[x][y]+1);
                        vis[x_][y_]=true;
                        read_into(x_,y_);
                    }
                }
            }
        }
    }
}