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 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0 - 样例输出
-
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)#include "bits/stdc++.h" using namespace std;
const int maxN = ;
const int INF = ;
struct Shortest_Path { int x , y ; } SP[ maxN * maxN ] ; const int dx [ ] = { , - , , } ;
const int dy [ ] = { , , - , } ;
typedef long long QAQ ; int l , ans = INF ; int mp[ maxN ][ maxN ] ;
int vis[ maxN ][ maxN ] ; void Record ( ) {
for ( int i= ; i< ; ++i ) {
for ( int j= ; j< ; ++j ) {
if ( vis[ i ][ j ] ) {
SP[ ++l ].x = i ;
SP[ l ].y = j ;
} }
}
}
void DFS ( const int xi , const int yi , const int step ) {
if ( mp[ xi ][ yi ] == || step > ans ) return ;
if( xi == && yi == ) {
ans = min ( ans , step ) ;
l = ;
Record ( ) ;
return ;
}
for(int i = ; i < ; ++i ) {
int xx = xi + dx [ i ] ;
int yy = yi + dy [ i ] ;
if ( !vis[ xx ][ yy ] && mp[ xx ][ yy ] == ) {
if ( xx < || yy < || xx > || yy > ) continue ;
vis[ xx ][ yy ] = true ;
DFS( xx , yy , step + ) ;
vis[ xx ][ yy ] = false ;
}
}
} int main ( ) {
for ( int i= ; i< ; ++i ){
for ( int j= ; j< ; ++j ) {
scanf ( "%d" , &mp[ i ][ j ] ) ;
}
}
vis[ ][ ] = true;
DFS ( , , ) ;
for ( int i= ; i<=l ; ++i )
printf ( "(%d, %d)\n" , SP[ i ].x , SP[ i ].y ) ; return ;
}2016-10-19 15:39:47