7084  迷宫问题

描述

定义一个二维数组： 

int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出

左上角到右下角的最短路径，格式如样例所示。

样例输入

0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

样例输出

(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)

1 #include "bits/stdc++.h" 2  3 using namespace std; 4 const int maxN = 55 ;  5 const int INF = 2147483647 ; 6 struct Shortest_Path { int x , y ; } SP[ maxN * maxN ] ; 7  8 const int dx [ ] = { 1 , -1 , 0 , 0 } ; 9 const int dy [ ] = { 0 , 0 , -1 , 1 } ;10 typedef long long QAQ ;11 12 int l , ans = INF ;13 14 int mp[ maxN ][ maxN ] ;15 int vis[ maxN ][ maxN ] ;16 17 void Record ( ) {18         for ( int i=0 ; i<5 ; ++i ) {19                 for ( int j=0 ; j<5 ; ++j ) {20                         if ( vis[ i ][ j ] ) {21                                 SP[ ++l ].x = i ; 22                                 SP[ l ].y = j ;23                         }24                          25                 }26         }27 }28 void DFS ( const int xi , const int yi , const int step ) {29         if ( mp[ xi ][ yi ] == 1 || step > ans ) return ;30         if( xi == 4 && yi == 4 ) {31                 ans = min ( ans , step ) ;32                 l = 0 ;33                 Record ( ) ;34                 return ;35         }36         for(int i = 0; i < 4; ++i ) {37                 int xx = xi + dx [ i ] ;38                 int yy = yi + dy [ i ] ;39                 if ( !vis[ xx ][ yy ] && mp[ xx ][ yy ] == 0 ) {40                         if ( xx < 0 || yy < 0 || xx > 4 || yy > 4 ) continue ; 41                         vis[ xx ][ yy ] = true ;42                         DFS( xx , yy , step + 1 ) ;43                         vis[ xx ][ yy ] = false ;44                 }45         }46 }47 48 int main ( ) {49         for ( int i=0 ; i<5 ; ++i ){50                 for ( int j=0 ; j<5 ; ++j ) {51                         scanf ( "%d" , &mp[ i ][ j ] ) ; 52                 }53         }54         vis[ 0 ][ 0 ] = true;55         DFS ( 0 , 0 , 1 ) ;56         for ( int i=1 ; i<=l ; ++i ) 57                 printf ( "(%d, %d)\n" , SP[ i ].x , SP[ i ].y ) ;58         59         return 0;60 }

2016-10-19 15:39:47