迷宫求解是一个经典的程序设计问题，目的是求出从入口到出口的所有路径。通常用“穷举回溯”的方法，即从入口出发，顺着某一个方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直到所有可能的通路都探索为止。
探索路的过程中java 走迷宫栈的算法 数据结构学习笔记（六）迷宫求解，为了保证在任何位置上都能沿路返回，显然需要一个后进先出的存储结构来保存从入口到当前位置的路径坐标，因此在迷宫求解算法中，应用“栈”的结构是自然的事。
一、栈的基本操作：
我们首先复习一下栈的基本操作：
（1）构造一个空栈。初始化成功则返回OK，否则返回ERROR。
int InitStack(SqStack *p) {
p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
if (p->base == NULL) return ERROR; //内存分配失败
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
return OK;
（2）判断栈中是否含有效的数据
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return OK;
else return ERROR;
（3）顺序栈进栈，将元素e压入到栈顶。
int Push(SqStack *p, StackType e) {
//插入元素e为新的栈顶元素
if ((p->top - p->base) >= p->stacksize) //栈满，追加储存空间
{
p->base = (StackType*)realloc(p->base,(p->stacksize + STACKINCREMENT) * sizeof(StackType));
if (p->base == NULL) return ERROR;// 储存空间分配失败
p->top = p->base + p->stacksize;
p->stacksize += STACKINCREMENT;
}
*(p->top) = e;
(p->top)++;
return OK;
（4）顺序栈出栈，将元素e弹出
int Pop(SqStack p, StackType e) {
//若栈不空，则删除p的栈顶元素，用e返回其值
if (p->top == p->base) return ERROR;
--(p->top);
*e = *(p->top);
return OK;
二、迷宫寻路设计思路：
以下图所示，图中绿色方块为通道，蓝色方块为墙壁，所求路径必须是简单路径，即在求得路径上不能重复出现同一通道方块。
6-1
1．物理存储结构：
①迷宫数据存储于一个结构体中，数据值放置于二维数组中，其中“0”代表墙值，“1”代表通路。由于迷宫被表示为二维数组，所以，在任何时刻，迷宫中的位置都可以用行(x)，列(y)坐标来描述。代码如下：
typedef struct {
int x; //行值
int y; //列值
② 路径存储于一个栈中，最好采用顺序栈存储，采用链栈，队列也可，各有好处，本次先讨论顺序栈存储。
③ 将路径的坐标点（x、y)，路径的方向(初始值为-1)，存放于一个结构体中。
//栈的元素类型
typedef struct
{
int id; //通道块在路径上的序号
PosType seat; //在迷宫中的坐标位置
int di; //从当前通道块走向下一位置的“方向”
} SElemType;
//顺序栈的结构
typedef struct {
StackType *base; //在构造之前和销毁之后，base的值为NULL
StackType *top; //栈顶指针
int stackSize; //当前已分配的存储空间，以元素为单位
2、逻辑实现思路
6-2
按上图所示，目的是寻找出路java 走迷宫栈的算法，假设“当前位置”是遍历过程中某一时刻所在图中的位置，则求迷宫中一条从进口到出口路径的中心思想是：
（1）若当前位置“可通”，则纳入“当前路径”，把当前位置（x,y)及方向信息入栈，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；
（2）若当前位置“不可通”，则应顺着“来路返回”退回到“上一方块”然后朝着“来向”之外的三个方向继续探索；
（3）若该通道方块四周四个方块都“不可通”，即应从“当前路径”上删除该通道方块信息，即“出栈”。
这里要注意两点：
（1）所谓“下一位置”，指“当前位置”的四个方向（东，西，南、北）上相邻的方块。
（2）假设以栈记录“当前路径”则栈顶中存放的是“当前路径上最后一个通道方块”。由些“纳入路径”的操作就是“入栈”；从当前路径上删除前一通道的操作即为“出栈”。
所以迷宫求解出口问题算法描述以下：
Do{
若当前位置可通，
则{
当前位置信息（位置，方向）插入栈顶
若该位置是出口位置，则探索结束；
否则切换到“下一位置”（默认以东邻方向为新的位置)
}
否则，
若栈不空并且栈顶位置还有其他方向未探索过，
则寻找栈顶（当前位置）的下一个位置（沿顺时针方向）
若栈不空但栈顶位置的四个方向均一不相通
则{ 删除栈顶位置，退回上一通道方块
若栈不空，则重新测试当前栈顶的下一位置
直到找到一个可通的相邻通道或出栈至栈空；
}
需要说明的是，所谓的当前位置可通，指的是未曾走到过的通道块，即要求该方块位置栈记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置压入”；
“从当前路径上删除前一块通道块”的操作即为“弹出”。不仅是通道块，而且不在当前路径上(否则路径不是简单路径)，也不是曾经纳入过路径的通道块(否则只能在死胡同内转圈)。
三、迷宫寻路算法实现
走迷宫的过程跟进栈出栈一样，移动一个方位就进栈，走不动了java 走迷宫栈的算法，就原路退回，就相当于退栈，所以我们首先用一个多维数组来构建迷宫。代码如下：
<p><pre>void InitMaze()
{
int i, j, x1, y1;
printf("请输入迷宫的行数，列数(包括外墙):");
scanf("%d%d", &x, &y);
for (i = 1; i < x - 1; i++)
for (j = 1; j < y - 1; j++)
maze[i][j] = 1; //定义通道初值为1
printf("请输入迷宫内墙单元数:");
scanf("%d", &j);
printf("请依次输入迷宫内墙每个单元的行数，列数:\n");
for(i=1;i