迷宫问题的研究
20##-2005（2）学期 ****班 学号：** 姓名：*** 指导老师：
[问题描述]
以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得到没有通路的结论。
[基本要求]
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序，求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（3，2，3）（3，1，2）…
[测试数据]
迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。
1 2 3 4 5 6 7 8
[实现提示]
计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。
[选作内容]
（1）编写递归形式的算法，求得迷宫中所有可能的通路；
（2）以方阵形式输出迷宫及其通路。
题目：编制一个求解迷宫通路的程序，对其机制进行研究。
一、需求分析
（1）以二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](o≤n+1)及Maze[i][0]和Maze[i][n+1] (o≤m+1)为添加的一圈障碍。数组中以元素值为0表示通路，1表示障碍，限定迷宫的大小m,n≤10。
（2）用户以文件的形式输入迷宫的数据；文件中第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，同一行中的两个数字之间用空白字符相隔。
（3）迷宫的入口位置和出口位置可由用户随时设定。
（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符@表示“死胡同”，即曾途经然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。
（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。
（6）测试数据见原题，当入口位置为（1，1），出口位置为（9，8）时，输出数据应为：
（7）程序执行的命令为：
1）创建迷宫；2）求解迷宫；3）输出迷宫的解。
二、概要设计
1．设定栈的抽象数据类型定义：
ADT Stack {
数据对象：D={ai|ai∈CharSet,i=1,2,…,n,n≥o}
数据对象：R1={<aI-1,aI>| aI-1,aI∈D,i=2,…,n}
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。
DestroStack(&S)
初始条件：栈S已存在。
操作结果：销毁栈S。
ClearStack(&S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackLength(S)
初始条件：栈S已存在。
操作结果：返回栈S的长度。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。
GetTop(S,&e)
初始条件：栈S已存在。
操作结果：若栈S不空，则以e返回栈顶元素。
Push(&S,e)
初始条件：栈S已存在。
操作结果：在栈S的栈顶插入新的栈顶元素。
Pop(&S,&e)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素，并以e返回其值。
StackTraverse(S,visit( ))
初始条件：栈S已存在。
操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit( )。
}ADT Stack
2．设定迷宫的抽象数据类型为：
ADT Stack{
数据对象：D={ aij|aI,j∈{′′、′#′、′@′′*′},0≤i≤m+1,o≤j≤n+1,m,n≤10}
数据对象：R={ROW,COL}
ROW={<ai-1,j,ai,j>|aI-1,j,aI,j∈D,i=1,…,m+1,j=0,…n+1}
DOL={<ai,j-1,ai,j>|aI,j-1,aI,j∈D,i=0,…,m+1,j=1,…n+1}
基本操作：
InitMaze(&M,a,row,col)
初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。
操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符#表示障碍，并在迷宫四周加上一圈障碍。
MazePath(&M)
初始条件：迷宫M已被赋值。
操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以字符“*”表示路径上的位置，字符“@”表示“死胡同”；否则迷宫的状态不变。
PrintMaze(M)
初始条件：迷宫M已存在。
操作结果：以字符形式输出迷宫。
}ADT maze
3．本程序包含三个模块
1）主程序模块：
void main( )
{
初始化；
do{
接受命令；
处理命令；
}while(命令！=“退出”)；
}
2）栈模块——实现栈抽象数据类型
3）迷宫模——实现迷宫抽象数据类型
各模块之间的调用关系如下：
主程序模块
迷宫模块
栈模块
4．求解迷宫中一条通路的伪码算法：
设定当前位置的初值为入口位置；
do{
若当前位置可通，
则{将当前位置插入栈顶； // 纳入路径
若该位置是出口位置，则结束； // 求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置；
}
否则{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相领块；若栈不空但栈顶位置的四周均不可通，
则{删去栈顶位置； //后退一步，从路径中删去该通道块，
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}while(栈不空)；
{栈空说明没有路径存在}
三、详细设计
1．坐标位置类型
typedef struct
int r,c; //迷宫中r行c列的位置
}PosType；
2．迷宫类型
typedef struct
int m,n;
char arr[RANGE][RANGE]; //各位置取值＇＇，＇#＇，＇@＇或＇*＇
}MazeType
void InitMaze(Maze Type &maze,inta[][],int row,int col)
//按照用户输入的row行和col列的二维数组（元素值为0或1）
//设置迷宫maze的初值，包括加上边缘一圈的值
bool MazePath(MazeType &maze,PosType start,PosType end)
//求解迷宫maze中，从入口start到出口end的一条路径，
//若存在，则返回TRUE；否则返回FALSE
void PrintMaze(MazeType maze)
//将迷宫以字符型方阵的形式输出到标准输出文件上
3．栈类型
typedef struct{
int step; //当前位置在路径上的“序号”
PosType seat; //当前的坐标位置
DirectiveType di; //往下一坐标位置的方向
}ElemType; //栈的元素类型
typedef struct NodeType{
EoemType data;
NodeType *next;
}NodeType,*LinkType; //结点类型，指针类型
typedef struct{
LinkType top;
Int size;
}Stack; //栈类型
栈的基本操作设置如下：
void InitStack(Stack &S)
//初始化，设S为空栈（S.top=NULL）
void DestroyStack(S.tack &S)
//销毁栈S，并释放所占空间
void ClearStack(Stack &S)
//将S清为空栈。
int StackLength(Stack S)
//返回栈S的长度S.size
Status StackEmpty(Stack S)
//若S为空栈（S.top= =NULL）,则返回TRUE；否则返回FALSE
Status GetTop(StackS,ElemTypee)
//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE
Status Push(Stack &S,ElemType e)
//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；
//否则栈不变，并返回FALSE
StatusPop(Stack &S,ElemType &e)
//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，
//否则返回FALSE
void StackTraverse(Stack S,Status(*visit)(ElemType e)
//从栈底到栈顶依次对S中的每个结点调用函数visit
其中部分操作的算法：
Status Push(Stack &S,ElimType e)
{
//若分配空间成功，则在S的栈顶插入新的栈顶元素e,并返回TRUE；
//否则栈不变，并返回FALSE
if(MakeNode(p,e)){
P .next=S.top;S.top=p;
S.size++;feturn TRUE;
}
else return FALSE
Status Pop(Stack&S,ElemType&e)
{
//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，
//否则返回FALSE，且e无意义
if(StackEmpty(S)feturnFALSE;
else{
P=S.top;S.top=S.top->next;
E=P->data;S.size-;return TRUE;
}
}
4．求迷宫路径的伪码算法：
Status MazePath(MazeType maze,PosType start,PosType end)
{
//（从栈底到栈顶为从入口到出口的路径），并返回TRUE；否则返回FALSE。
InitStack(S);curpos=start; //设定“当前位置”为“入口位置”
Curstep=1;found=FALSE; //探索第一步
do{
if(Pass(maze,crupos)){
//当前位置可以通过，即是未曾走到过的通道块留下足迹
FootPrint(maze,crupos);
e=(curstep,crupos,1);
Push(S,e); //加入路径
if(Same(crupos,end))found=TRUE; //到达终点（出口）
else{
curpos=NextPos(crupos,1); //下一位置是当前位置的东邻
curstep--; //探索下一步
}//else
}//if
else //当前位置不能通过
if(!StackEmpty(S){
Pop(S,e);
While(e.di= =4&&!StackEmpty(S)){
MarkPrint(maze,e.seat);Pop(S,e);
Curstep--; //留下不能通过的标记，并退回一步
}//while
if(e.di<4){
e.di++;Prsh(S,e); //换下一个方向探索
curpos=NextPos(e.seat,e.di); //设定当前位置是该新方向上的相邻块
}//if
}//if
}while(!StackEmpty(S)&&!found);
return found;
}//MazePath
5．主函数和其他函数的伪码算法
void main( )
{
//主程序
Initialization( ); //初始化
do{
ReadCommand(cmd); //读入一个操作命令符
Interpret(cmd); //解释执行操作命令符
}while(cmd!=＇Q＇);
}//main
void Initialization( )
{
//系统初始化
clrscr( ); //清屏
在屏幕上方显示操作命令清单：
CreatMaze_c MazePath_m PrintMaze_p Quit_q;
在屏幕下方显示操作命令提示框；
}//Initialization
void Read Cimmand(char &cmd)
{
//讯入操作命令符
显示键入操作命令符的提示信息；
do{
cmd=getche( )
}while(cmd([＇c＇,＇C＇,＇m＇,＇M＇,＇p＇,＇P＇,＇q＇,＇Q＇]);
}//ReadCommand
void Interpret(char cmd)
{
//解释执行操作命令cmd
switch(cmd){
case＇c＇,＇C＇:提示用户输入“迷宫数据的文件名filename”;
从文件读入数据分别存储在rnum,cnum和二维数组a2中；
InitMaze(ma,a2,rnum,cnum); //创建迷宫
输出迷宫建立完毕的信息；
break;
case＇m＇,＇M＇:提示用户输入迷宫的入口from和出口term的坐标位置；
if(MazePath(ma,from,term)) //存在路径
提示用户察看迷宫；
else输出该迷宫没有从给定的入口到出口的路径的信息；
break;
case＇p＇,＇P＇:PrintMaze(ma); //将标记路径信息的迷宫输出到终端
}//switch
}//Interpret
6．函数的调用关系图反映了演示程序的层次结构：
四、调试分析
1．本次作业比较简单，只有一个核心算法，即求迷宫的路径，所以总的调试比较顺利，只在调试MazePath算法时，遇到两个问题：其一是，起初输出的迷宫中没有加上＇@＇的记号，后发现是因为在MarkPrint函数中的迷宫参数丢失“变参”的原因；其二是，由于回退时没有将curpos随之减一，致使栈中路径上的序号有错。
2．栈的元素中的step域没有太多用处，可以省略。
3．StackTravers在调试过程中很有用，它可以插入在MazePath算法中多处，以察看解迷宫过程中走的路径是否正确，但对最后的执行版本没有用。
4．本题中三个主要算法：InitMaze,MazePath和PrintMaze的时间复杂度均为0（m×n）,本题的空间复杂度亦为0（m×n）（栈所占最大空间）。
5．经验体会：借助DEBUG 调试器和数据观察窗口，可以加快找到程序中疵点。
五、用户手册
1．本程序的运行环境为DOS操作系统，执行文件为：TestMaze.exe。
2．进入演示程序后，即显示文本方式的用户界面：
3．进入“产生迷宫（CreateMaze）”的命令后，即提示键入迷宫数据的文件名，结束符为“回车符，该命令执行之后输出“迷宫已建成”的信息行。
4．进入“求迷宫路径（MazePath）”的命令后，即提示键入入口位置（行号和列号，中间用空格分开，结束符为“回车符”和出口位置（行号和列号，中间用空格分开，结束符为“回车符”），该命令执行之后输出相应信息。请注意：若迷宫中存在路径，则执行此命令之后，迷宫状态已经改变，若需要重复执行此命令，无论是否改变入口和出口的位置，均需重新输入迷宫数据。
5．输入“显示迷宫”的命令后，随即输出当前的迷宫，即迷宫的初始状态或求出路径之后的状态。
六、测试结果
三组测试数据和输出结果分别如下：
1．输入文件名为：m1.dat,其中迷宫数据为：
3 2
0 0
0 0
0 0
入口位置：1 1
出口位置：3 2
求解路径后输出的迷宫：
2．输入文件名：m2.dat，其中迷宫数据：
3 4
0 0 0 0
0 0 1 1
0 0 0 0
入口位置：1 1
出口位置：3 4
求解路径后输出的迷宫：
3．输入文件名：m3.dat，其中迷宫数据同题目中的测试数据。
入口位置：1 1
出口位置：9 8
求解路径后输出的迷宫正确，并和需求分析中所列相同。
4．输入文件名：m4.dat的，其中迷宫数据：
4 9
0 0 0 0 0 0 1 0 0
0 1 0 0 0 1 0 0 0
0 0 1 1 1 0 0 1 1
0 0 1 1 1 0 1 0 0
入口位置：1 1
出口位置：4 9
输出信息：此迷宫从入口到出口没有路径。
七、附录
源程序文件名清单：
base.H //公用的常量和类型
stkpas.H //栈类型
maze.H //迷宫类型
testmaze.C //主程序