Question

数据结构的编程问题：迷宫问题．

求迷宫中从入口到出口的所有路径．以一个m乘n的长方阵表示迷宫，0和1分别表示迷宫中的通路和路障．设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或者没有通路的结论
采用”穷举求解”的方法，从入口出发，顺某一个方向先前探索，若能走通，则继续往前走，否则沿原路退回，换一个 方向再继续探索，直到所有可能得通路都探索为止．可以用二维树组作为存储迷宫数据，通常设定下标为（1， 1）为入口点，出口点下标为（n，n）．为了处理方便可以在迷宫四周加一圈障碍．

Answer 1

直接dfs
#include <stdio.h>

#define Limit_Size 500

int map[ Limit_Size ][ Limit_Size ];
int n, m;
int visit[ Limit_Size ][ Limit_Size ];
int success = 0, count;

struct road
{
int x, y;
};

road stack[ Limit_Size * Limit_Size ];

void init( )
{
int i, j;
char t[ Limit_Size ];
printf("Please input m and n:\n");
scanf("%d%d", &m, &n);
printf("Please input the map:\n");
for ( i = 1; i <= m; i++ )
{
scanf("%s", t);
for ( j = 1; j <= n; j++ )
{
visit[ i ][ j ] = 1;
map[ i ][ j ] = t[ j - 1 ] - '0';
}
}
for ( i = 0; i <= n + 1; i++ )
map[ 0 ][ i ] = map[ m + 1 ][ i ] = 1;
for ( i = 0; i <= m + 1; i++ )
map[ i ][ 0 ] = map[ i ][ n + 1 ] = 1;
visit[ 1 ][ 1 ] = 0;
}

void dfs( int x, int y, int step )
{
if ( success )
return ;
stack[ step ].x = x;
stack[ step ].y = y;
if ( x == n && y == n )
{
count = step;
success = 1;
return ;
}
if ( !map[ x - 1 ][ y ] && visit[ x - 1 ][ y ] )
{
visit[ x - 1 ][ y ] = 0;
dfs( x - 1, y, step + 1 );
visit[ x - 1 ][ y ] = 1;
}
if ( !map[ x + 1 ][ y ] && visit[ x + 1 ][ y ] )
{
visit[ x + 1 ][ y ] = 0;
dfs( x + 1, y, step + 1 );
visit[ x + 1 ][ y ] = 1;
}
if ( !map[ x ][ y - 1 ] && visit[ x ][ y - 1 ] )
{
visit[ x ][ y - 1 ] = 0;
dfs( x, y - 1, step + 1 );
visit[ x ][ y - 1 ] = 1;
}
if ( !map[ x ][ y + 1 ] && visit[ x ][ y + 1 ] )
{
visit[ x ][ y + 1 ] = 0;
dfs( x, y + 1, step + 1 );
visit[ x ][ y + 1 ] = 1;
}
}

void print( )
{
int i;
printf("(%d, %d)", stack[ 0 ].x, stack[ 0 ].y);
for ( i = 1; i <= count; i++ )
printf("->(%d, %d)", stack[ i ].x, stack[ i ].y);
printf("\n");
}

int main( )
{
init( );
dfs( 1, 1, 0 );
print( );
return 0;
}