迷宫问题是一道经典的回溯算法问题，给定一个迷宫矩阵，矩阵中的1表示障碍，0表示可走通路，给定迷宫入口出口，要求寻找从入口穿过迷宫到达出口的所有路径，有则输出，无则给出提示。一本合格的数据结构教科书一般都会介绍迷宫问题，网上的分析也是铺天盖地，这里就不再赘述重复的内容了。废话不多说，简单介绍一下程序，然后上代码。
该程序用二维数组表示迷宫，用另一个二维数组记录迷宫中的位置是否已经走过，同时用一个链式栈存放搜索出的临时路径。程序从迷宫入口开始试探，随着回溯试探过程的进行，链式栈的长度不断变化，当试探到迷宫出口时，链表中存放的就是一条完整的穿过迷宫的路径了，输出路径后回溯，继续试探下一条路径，当回溯到入口时没有新的可走方向时整个回溯试探的过程也就结束了。链表节点中除了存放被路径连接的各单元的行列标外，还存放有由该节点代表的单元前往该节点的后继节点代表的单元的方向，这么做是为了方便回溯操作的进行。
为方便起见，程序中迷宫的入口是固定的，为左上角单元，出口同样固定，为右下角单元。这并不妨碍程序的普适性，只要稍加修改就可以使程序适用于任意给定的出口和入口的情形。
啰嗦了这么半天，下面该上代码了，代码用C语言编写，具体如下。
#include <stdio.h>
#include <malloc.h>
void convert(int *i, int *j, int k); //将当前单元行标列标i,j更新为方向k所指向的相邻单元的行标列标
int boundary(int i, int j, int d, int n, int m); //检查(i,j)单元在d方向上是否为迷宫边界,是返回0，不是返回1
int barrier(int i, int j, int d, int **p); //检查(i,j)单元在d方向上是否遇到障碍，是返回0，不是返回1
int visit(int i, int j, int d, int **t); //检查(i,j)单元在d方向上的相邻单元是否已走过，是返回0，不是返回1
int direction(int i, int j, int d, int n, int m, int **p, int **t); //检查(i,j)单元在d方向上是否可走,可走返回1，否则返回0
int trial(int i, int j, int k, int n, int m, int **p, int **t); //在(i,j)单元上从k方向的下一个方向起寻找下一个可走方向,找到返回方向号，否则返回0
void main ()
{
int i, j, k; //i,j为单元位置标识,k为方向参数
int m, n; //m为迷宫行数,n为迷宫列数
int flag, Num; //flag标志是否存在走出迷宫的路径,Num为找到的路径序号
int min, max;
char *q;
int **p, **t; //p指向表示迷宫的二维数组,t指向记录迷宫中的每个位置是否已走过的二维数组
struct Record //表示路径节点的结构体类型
{
int x;
int y; //节点对应单元的行列标
int sign;
int mark; //记录当前节点的后继节点对应的单元相对于当前节点对应的单元的方向
struct Record *next;
struct Record *before;
};
struct Record *head, *psnewbe, *psnewaf, *current;
typedef struct Record Record1;
struct Long
{
int Num;
int length;
struct Long *next;
};
struct Long *head1, *psnew1, *p1;
typedef struct Long Long1;
printf ("please input the number of row and col of the Maze matrix\n");
printf ("please enter the row\n");
printf ("row=");
scanf ("%d", &m); //输入迷宫矩阵行列数
printf ("please enter the col\n");
printf ("col=");
scanf ("%d", &n);
q=(char *) malloc((n+1)*sizeof(char));
p=(int **) malloc(m*sizeof(int *));
for (i=0; i<m; i++)
{
p[i]=(int *) malloc(n*sizeof(int));
printf("please input the %dnd row of Maze matrix\n", i+1); //初始化迷宫矩阵,0表示可走,1表示障碍
scanf ("%s", q);
for (j=0; j<n; j++)
*(p[i]+j)=q[j]-48;
}
t=(int **) malloc(m*sizeof(int *));
for (i=0; i<m; i++)
{