NOI 题库 2753

2753 走迷宫

描述

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

输入

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用'.'表示，有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

样例输入

5 5

..###

#....

#.#.#

#.#.#

#.#..

样例输出

 #include "bits/stdc++.h"

 using namespace std;

 const int maxN =  ;

 const int INF =  ;

 const int dx [ ] = {  , - ,  ,  } ;

 const int dy [ ] = {  ,  , - ,  } ;

 typedef long long QAQ ;

 int r , c , ans = INF ;

 char mp[ maxN ][ maxN ] ;

 bool vis[ maxN ][ maxN ] ;

 void DFS ( const int xi , const int yi , const int step ) {

         if ( mp[ xi ][ yi ] == '#' || step > ans ) return ;//当当前答案比已有答案差，不再继续搜索

         if( xi == r && yi == c ) {

                 ans = min ( ans , step ) ;

                 return ;

         }

         for(int i = ; i < ; ++i ) {

                 int xx = xi + dx [ i ] ;

                 int yy = yi + dy [ i ] ;

                 if ( !vis[ xx ][ yy ] && mp[ xx ][ yy ] == '.' ) {

                         vis[ xx ][ yy ] = true ;

                         DFS( xx , yy , step +  ) ;

                         vis[ xx ][ yy ] = false ;

                 }

         }

 }

 void Init ( ){

         for ( int i= ; i<=r+ ; ++i )

                 for ( int j= ; j<=c+ ; ++j )

                         if ( i== || i == r+ || j== || j== c+ ) mp[ i ][ j ] = '#' ;

 }

 int main ( ) {

         scanf ( "%d%d" , &r , &c ) ;

         Init ( );

         getchar ( ) ;

         for ( int i= ; i<=r ; ++i ){

                 for ( int j= ; j<=c ; ++j ) {

                         mp[ i ][ j ] = getchar ( ) ;

                 }

                 getchar ( ) ;

         }

         vis[  ][  ] = true;

         DFS (  ,  ,  ) ;

         cout << ans << endl ;

         return ;

 }

2016-10-18 18:20:22

(完)

2753 走迷宫

相关文章