4迷宫问题以一个m
的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，
对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求：（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组ijd的形式输出，其中ij指示迷宫中的一个坐标，d表示走到下一坐标的方向。
（2）测试几组数据，数据的规模由小变大，即网格越来越小，障碍越来越复杂。拓展要求：实现该问题的可视化界面，用鼠标点击即可一步步走出迷宫。提示：计算机解迷宫问题通常采用“穷举求解”方法。
1．需求分析
以一个m
的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。输入迷宫的长和宽，以方阵形式输出迷宫及其通路。
2．设计
21设计思想（1）数据结构设计以链表作存储结构的栈类型原因：便于探索迷宫路径（2）算法设计先按自己的意图创建一个迷宫矩阵，接着创建两个以链表作存储结构的栈p和q，p存储路径，而q存储探索路径，当有新位置时就把q中栈顶元素传给p，没有时就出栈，即遇到死路时返回。总体上包括三个模块，CreatMaze是创建一个迷宫，Fi
dMaze找到迷宫路径。Pri
t则是打印这个路径。主程序的流程图
1Mai

CreatMaze01
Fi
dMaze
探索失败
0
是否继续
退出
探索成功
打印
22设计表示（1）函数调用关系图如上图（2）函数接口规格说明I
tCreatMazei
tmi
t
输入并获取迷宫
fBoolfi
dMaze（i
tmazei
tmi
t
）用于寻找迷宫从（00）到（m
）的路径
VoidPri
tPathStackp用于输出迷宫的路径
23详细设计主要算法的实现
boolFi
dMazei
tmazei
tmi
t
寻找迷宫maze中从（，）到（m
）的路径
到则返回true否则返回false

Stackqp
定义栈p存储路径q存探索迷宫的过程
TTemp1Temp2
i
txyloop
Temp1x1
Temp1y1
qPushTemp1
将入口位置入栈
pPushTemp1
maze111
标志入口位置已到达过
whileqempty
栈q非空，则反复探索

Temp2qGetPop
获取栈顶元素
ifpGetPopxqGetPopxpGetPopyqGetPopy
pPushTemp2
如果有新位置入栈，则把上一个探索的位置存入栈p
forloop0loop4loop探索当前位置的个相邻位置

xTemp2xmoveloop0计算出新位置x位置值
yTemp2ymoveloop1
计算出新位置y位置值
ifmazexy0
判断新位置是否可达

Temp1xx
Temp1yy
mazexy1
标志新位置已到达过
qPushTemp1
新位置入r