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

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

直接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