2018.9.4南海中学测试T1

**1、栅栏迷宫

田野上搭建了一个黄金大神专用的栅栏围成的迷宫。幸运的是，在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点，走出迷宫的最少步数）。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，黄金大神让你必须只会水平或垂直地在X或Y轴上移动，你不能从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）这是一个W=5,H=3的迷宫：

如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。
PROGRAM NAME: maze
INPUT FORMAT: (file maze.in)
第一行： W和H（用空格隔开）
第二行至第2*H+1行：每行2*W+1个字符表示迷宫
OUTPUT FORMAT: (file maze.out)
输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
SAMPLE INPUT
5 3

SAMPLE OUTPUT
9

题目很容易看懂，每个点到最近的出口都有一个最短路径，那么就求出所有点走出最近出口的最短路径的最大值。那么想法很简单，直接两个BFS就ok了。每次BFS保存走到这个格子的最小值，跑完两次之后找最大值就可以了。

然后这道题目和其他题目不同的是，它的图很奇怪，并不是经常见到的01图。观察这个图可得知，其实W一共有2*W+1这么大， H也只是有2*H+1这么大。然后奇数行都是墙，都不是能走的格子。还有一个最重要的问题，这个图之中还有空格。这个让我们保存这个图有一点难度。
所以我就像下面代码一样保存这个图：

    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;
        } 
    }

每次读入一个字符，用getchar（）不仅能读入空格，也能读入换行符。所以在读入完每一行的数据之后都要getchar()一下。然后就判断读入的是否是空格就ok了。

然后就是保存出口的问题了。这道题我一开始爆零就是因为找出口太片面了，认为出口肯定一个在上下，一个在右，所以两次BFS前现在上下找一个出口，或者在左右找一个出口。
这样明显是错误的嘛，所以找出口在输入的时候加上一条判断，如果是出口就保存，那就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;}

然后我在我错误的程序上修改后，测试完有一个点总是超时。而且这个图也是特别的奇葩。

这个图超级帅，超有规律，但是我就是超时了。比这个数据还大的数据我都不超时，就这个超时了。然后我调试的时候发现，我在BFS时死循环了。然后我看了很久，才发现我犯了一个错误，而且这个错误在我写BFS时也是很常见。
大家先看看我错误的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_);
                    }
                }
            }
        }
    }
}

先解释一下，能走的格子之间是有墙的，所以先判断距离为一的地方是否时墙，如果不是墙表示能走，所以就走两步，这是由于这道题才这么做的。

回归正题，那么这个BFS看上去没错的，但是导致了死循环，为什么呢？
看看我vis数组，标记的位置是在当执行到这个点的时候才标记为true。那么就会出现一个情况，我很多个点都能重复走到一个点，那么我这个点就一直入队，一直入一直入，所以导致了死循环。
解决办法很简单，当发现这个可以走时直接标记为true，这样就不会出现这种重复入队的情况了。

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_);
                    }
                }
            }
        }
    }
}