这个迷宫的路径不是唯一的，因此从不同方向开始试探执行结果也可能会不唯一。我写的是参考书上的，共有八个方向可以试探。
栈解决迷宫主要的几个问题：
1.迷宫的存储
2.栈的设计
3.试探方向
4.不重复到达某点，即不陷入死循环
如果对算法有什么疑问，或是我的回答有错误的地方，可以Hi我。
#define LINES 9 // 定义行数
#define COLS 8 // 定义列数
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct{
int line;
int col;
}MOVE; // 定义试探方向的结构体
MOVE to[8] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; // 定义数组，存放8个试探方向
typedef struct{ // 行、列、方向构成的三元组
int x;
int y;
int d;
}DataType;
typedef struct node{
DataType element;
struct node * next;
}StackNode,*LinkStack;
LinkStack InitStack(LinkStack s); // 栈初始化
LinkStack PushStack(LinkStack,DataType *); // 入栈函数
LinkStack PopStack(LinkStack,DataType *); // 出栈函数
int EmptyStack(LinkStack s); // 判定栈空
int path(int maze[][COLS+2]); // 打印路径
void printpath(LinkStack s,DataType * t);
int main( void )
{
int i,j;
int maze[LINES+2][COLS+2] = // 定义存放迷宫的数组并初始化
{1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,1,1,
1,0,1,1,1,0,0,1,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,1,1,
1,0,1,1,1,1,0,0,1,1,
1,1,1,0,0,0,1,0,1,1,
1,1,1,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1
};
for(i=1;i<LINES+1;i++)
{
for(j=1;j<COLS+1;j++){
if( 0 == maze[i][j] ){
printf("□");
}
else{
printf("■");
}
}
printf("\n");
}
if( path(maze) ){
printf("找到一条路径\n");
for(i=1;i<LINES+1;i++)
{
for(j=1;j<COLS+1;j++)
{
if( 0 == maze[i][j] ){
printf("□");
}
else if( 1 == maze[i][j]){
printf("■");
}
else{
printf("☆");
}
}
printf("\n");
}
}
else{
printf("迷宫无路径\n");
}
return 0;
}
LinkStack InitStack(LinkStack s)
{
return NULL;
}
LinkStack PushStack(LinkStack s,DataType * t)
{
StackNode * p;
p = NULL;
p = (StackNode *)malloc(sizeof(StackNode));
if(!p){
printf("申请结点失败\n");
exit(1);
}
p->element = *t;
p->next = s;
s = p;
return s;
}
LinkStack PopStack(LinkStack s,DataType *t)
{
StackNode * p = NULL;
if( EmptyStack(s) ){
printf("栈空\n");
return NULL;
}
p = s;
*t = p->element;
s = s->next;
free(p);
p = NULL;
return s;
}
int EmptyStack(LinkStack s)
{
if( NULL == s ){
return 1;
}
return 0;
}
int path(int maze[][COLS+2])
{
int i,j,x1,y1,v;
DataType temp;
LinkStack top;
temp.x = 1;
temp.y = 1;
temp.d = -1;
top = InitStack(top);
top = PushStack(top,&temp);
while( !EmptyStack(top) )
{
top = PopStack(top,&temp);
// 入口为(1,1)，从0方向开始试探
x1 = temp.x;
y1 = temp.y;
v = temp.d + 1;
while( v < 8 )
{
i = x1 + to[v].line;
j = y1 + to[v].col;
if( 0 == maze[i][j] ){ // 到达新点
temp.x = x1;
temp.y = y1;
temp.d = v;
top = PushStack(top,&temp); // 坐标及方向入栈
x1 = i;
y1 = j;
maze[x1][y1] = -1; // 对已经到过的点做标记
if( x1 == LINES && y1 == COLS ){ // 到达出口
printpath(top,&temp); // 打印路径
return 1;
}
else{
v = 0;
}
}
else{
v++;
}
}
}
return 0;
}
void printpath(LinkStack s,DataType * t)
{
while( !EmptyStack(s) )
{
printf("(%d, %d, %d)\n",s->element.x,s->element.y,s->element.d);
s = PopStack(s,t);
}
}
温馨提示：答案为网友推荐，仅供参考