注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

ZSTU 3427 Amazing Mazes  

2011-11-06 19:04:37|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.zstu.edu.cn:8080/JudgeOnline/showproblem?problem_id=3427

Amazing Mazes

Time Limit:5000MS  Memory Limit:65536K
Total Submit:109 Accepted:56

Description

You are requested to solve maze problems. Without passing through these mazes, you might not be able to pass through the domestic contest!

A maze here is a rectangular area of a number of squares, lined up both lengthwise and widthwise, The area is surrounded by walls except for its entry and exit. The entry to the maze is at the leftmost part of the upper side of the rectangular area, that is, the upper side of the uppermost leftmost square of the maze is open. The exit is located at the rightmost part of the lower side, likewise.

In the maze, you can move from a square to one of the squares adjoining either horizontally or vertically. Adjoining squares, however, may be separated by a wall, and when they are, you cannot go through the wall.

Your task is to find the length of the shortest path from the entry to the exit. Note that there may be more than one shortest paths, or there may be none.

Input

The input consists of one or more datasets, each of which represents a maze.

The first line of a dataset contains two integer numbers, the width w and the height h of the rectangular area, in this order.

The following 2 × h ? 1 lines of a dataset describe whether there are walls between squares or not. The first line starts with a space and the rest of the line contains w ? 1 integers, 1 or 0, separated by a space. These indicate whether walls separate horizontally adjoining squares in the first row. An integer 1 indicates a wall is placed, and 0 indicates no wall is there. The second line starts without a space and contains w integers, 1 or 0, separated by a space. These indicate whether walls separate vertically adjoining squares in the first and the second rows. An integer 1/0 indicates a wall is placed or not. The following lines indicate placing of walls between horizontally and vertically adjoining squares, alternately, in the same manner.

The end of the input is indicated by a line containing two zeros.

The number of datasets is no more than 100. Both the widths and the heights of rectangular areas are no less than 2 and no more than 30.

Output

For each dataset, output a line having an integer indicating the length of the shortest path from the entry to the exit. The length of a path is given by the number of visited squares. If there exists no path to go through the maze, output a line containing a single zero. The line should not contain any character other than this number.

Sample Input

2 3   1  0 1   0  1 0   1  9 4   1 0 1 0 0 0 0 0  0 1 1 0 1 1 0 0 0   1 0 1 1 0 0 0 0  0 0 0 0 0 0 0 1 1   0 0 0 1 0 0 1 1  0 0 0 0 1 1 0 0 0   0 0 0 0 0 0 1 0  12 5   1 0 0 0 0 0 0 0 0 0 0  0 0 0 1 1 0 0 0 0 0 0 0   1 0 1 0 0 0 0 0 0 0 0  0 0 0 0 0 0 1 1 0 0 0 0   0 0 1 0 0 1 0 1 0 0 0  0 0 0 1 1 0 1 1 0 1 1 0   0 0 0 0 0 1 0 0 1 0 0  0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 0 0  0 0  

Sample Output

4  0  20  

Hint


ZSTU 3427 Amazing Mazes - 东月之神 - 东月之神

Source

asia 2010,Japan Domestic

 

        好久没有做题了,无聊看了下去年学校的校赛题,是广搜,于是便决定试试生锈了的算法。题目意思很好理解,就是给你方块的宽和高,即个数,每个方块的四边都有可能是墙,即如果是1的话就是墙,如果是0的话不是墙。从坐上角开始搜索,一直到最右下角,如果可以出来的话就算出最少的步数,如果被墙挡死的话就输出0。一开始,题意没有很明白,于是绕了好多的弯子。思路其实还是挺简单的,想法很多,我实现的比较死板,就是记录每一个方块的上下左右有没有墙,有的话标记为1,否则为0,于是在广搜的时候只要判断下是否可以加进队列了。

好久没有写代码了,就这样生疏了。下面是代码:

#include<stdio.h>
#include<string.h>
int a[71][71];
int b[31][31];
int mx[901][2];
int w[4][2] ={ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int hight, wide;
int head, tail;
struct squ
{
       int le, ri, up, dn;
       int num;
}squ1[31][31];

inline int bfs( int s1, int s2, int t1, int t2 )
{
     int x1, x2;
     head = 0;
     tail = -1;
     mx[0][0] = s1;
     mx[0][1] = s2;
    b[0][0] = 1;
    squ1[0][0].num = 1;
   while( tail < head )
   {
        tail++;
       s1 = mx[ tail ][ 0 ];
       s2 = mx[ tail ][ 1 ];
       if( s1 == t1 && s2 == t2 )
       {
            return b[ s1 ][ s2 ];
       }
      for( int i = 0; i < 4; i++ )
      {
           if(i == 0)
         {
             if(squ1[s1][s2].ri == 1)
             continue;   
        }
       else if(i == 1)
       {
           if(squ1[s1][s2].le == 1)
           continue;   
       }
      else if(i == 2)
      {
            if(squ1[s1][s2].dn == 1)
            continue;   
       }
      else if(i == 3)
      {
            if(squ1[s1][s2].up == 1)
           continue;   
      }
      x1 = s1 + w[i][0];
      x2 = s2 + w[i][1];
      if( squ1[x1][x2].num == 0 && x1 >= 0 && x1 < hight && x2 >= 0 && x2 < wide )
      {    
               squ1[x1][x2].num = 1;
              b[x1][x2] = b[s1][s2] + 1;
             ++head;
             mx[ head ][ 0 ] = x1;
             mx[ head ][ 1 ] = x2;
      }
    }
  }
return 0;

}

int main()
{
      int i, j, m, n, ii, jj;
      int g;
     while( scanf("%d%d", &wide, &hight) != EOF)
    {
          if(wide == 0 && hight == 0) break;
          memset( a, -1, sizeof( a ) );
          memset( b, 0, sizeof( b ) );
          memset( squ1, 0, sizeof( squ1 ) );
          memset(mx, 0, sizeof(mx));
         for(i = 0; i < 2 * hight - 1; i++)
              for(j = (i + 1) % 2; j < 2 * wide - 1; j += 2)
                   scanf("%d", &a[i][j]);      
         for(i = 0, ii = 0; i < 2 * hight - 1; i += 2, ii++)
        {
            for(j = 0, jj = 0; j < 2 * wide; j += 2, jj++)
           {
                if(a[i][j+1] == 1) squ1[ii][jj].ri = 1;
                if(j>0&&a[i][j-1] == 1) squ1[ii][jj].le = 1;
               if(a[i+1][j] == 1) squ1[ii][jj].dn = 1;
               if(i>0&&a[i-1][j] == 1) squ1[ii][jj].up = 1;  
          }
      }
     g = bfs( 0, 0, hight-1, wide-1);   
     printf("%d\n",g);
   }
return 0;
}

  评论这张
 
阅读(118)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017