1、栅栏迷宫

题目描述

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

+-+-+-+-+-+

|         |

+-+ +-+ + +

|     | | |

+ +-+-+ + +

| |     | 

+-+ +-+-+-+

如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。

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

善良的学长:样例输入可以复制进记事本或者文本文档这样看起来更加直观！！！=v=

思路

这题其实很可怕!!

最讨厌的就是去找入口出口。。我虽然过了那是数据太水……你看题目描述可不可以迷宫就建一半剩一半放那儿，那暴力找出入口就根本不行。

解决方法应该是在外面开一个出入口，然后搜索进入整个图，如果不是找到真正的出入口就会多走没必要的路，这样程序会自动剔除这种情况

搜索的时候注意一下向四面搜索每次走两步即可

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;struct note{    int x,y;}queue[200000];int p1[4][2]={
   {-2,0},{
   0,2},{
   2,0},{
   0,-2}};int p2[4][2]={
   {-1,0},{
   0,1},{
   1,0},{
   0,-1}};int a[500][500];int value[500][500];int head,tail,w,h;ifstream fin("maze.in");ofstream fout("maze.out");void input(){    fin>>w>>h;    w=w*2+1;h=h*2+1;    for (int i=1;i<=h;i++)    {        fin.get();        for (int j=1;j<=w;j++)        {            a[i][j]=fin.get();            if ( (i==1)&&(a[i][j]==' ') ) {tail++; queue[tail].x=i+1;queue[tail].y=j;  value[i+1][j]=1;}            if ( (i==h)&&(a[i][j]==' ') ) {tail++; queue[tail].x=i-1;queue[tail].y=j;  value[i-1][j]=1;}            if ( (j==1)&&(a[i][j]==' ') ) {tail++; queue[tail].x=i;queue[tail].y=j+1;  value[i][j+1]=1;}            if ( (j==w)&&(a[i][j]==' ') ) {tail++; queue[tail].x=i;queue[tail].y=j-1;  value[i][j-1]=1;}        }    }}void bfs(){    head=0;    int wx,wy,tx,ty,nx,ny; //wx,wy是p2的，tx,ty是p1的，nx,ny是现在的     while (head<=tail)    {        head++;        for (int i=0;i<=3;i++)        {            tx=queue[head].x+p1[i][0];ty=queue[head].y+p1[i][1];            wx=queue[head].x+p2[i][0];wy=queue[head].y+p2[i][1];            if ( (tx>0)&&(tx
          
           0)&&(ty
           
            best) best=value[i][j]; fout<
            
             <
            
           
          
         
        
       
      
     

结果