迷宫程序设计

1、（一）设计题目：迷宫（二）需求分析：任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷 宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、 源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；（三）概要设计：在迷宫设计中，由于不能使用递归则可以借助栈来实现在迷宫中的前进和 后退。同时在还需要设计迷宫的大小、迷宫的出入口、根据输入的入口来寻找迷 宫的出口，并把路径输出来。在这个编程中由于不知道所走路劲步数，所以采用了链式栈实现每一步的 移动，若找到出路则前进否则返回下一步改变方向来实现相关的移动，所以栈在 其间起到了工具

2、作用。在设计迷宫大小和出入口时，采用的是根据操作者实现的，但迷宫的具体 路障和通道是随机实现的。当然，重点是如何从出口来找出口。求迷宫的一条通路的伪码如下：设当前初始位置为出口：do（若当前位置可通，则将该位置插入到栈顶；/纳入路径若该位置为出口位置。则结束当前程序；/求得的路径放在栈中 否则切换当前位置的东临位置（即向右）为新的当前的位置；否则若栈不为空且栈顶元素尚有其他位置未被探索，则设定新的当前位置为 沿着顺时针旋转得到的栈顶位置的下一个临快；若栈不为空且栈顶位置的四周均不通（则删去栈顶元素；后退一步，从路径中删去该通块若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相 邻块或出栈至

3、栈空；/否则while（栈不为空）本程序的模块主程序从main （）函数中进行，包括输入迷宫的大小等信息，然后调用迷 宫模块，在迷宫模块中也调用了栈的模块。栈模块一一实现栈抽象数据类型迷宫模块一一实现迷宫抽象数据类型各模块之间的关系如下：主程序模块迷宫模块栈模块（四）详细设计1.坐标的位置类型：typedef struct （int r;int c;PosType;2.迷宫类型：typedef structint Col,Row;/迷宫的大小int arrRangleRangle; /0表示障碍，1表示是可走的通道，-1表示外界的围墙/2表示已经走过，3表示已经知道其不能通过MazeType;

4、void InitMaze（MazeType &M,int col,int row）按照用户的输入的行数row和列数col列的二维数组（元素值为1或0）设置迷宫的错初值，加上边缘的一圈的值void PrintMaze(MazeType M)根据已经进行二维数组的标记值来输出迷宫（或者其通路）bool Pass(MazeType M,PosType pos)/求解迷宫M中，从Start到end的一条路径/若存在则返回true,否则返回falseStack S;InitStack(S);PosType curpos=start;/设置当前坐标为入口位置；int curstep=1;当前的步数boo

5、l Find=false;是否找到出口ElemType e;doif(Pass(M,curpos)/如果当前位置可以通过(不是障碍物且未曾留下足迹)FootPrint(M,curpos);/在 当前位置标记为 2e.step=1;e.seat=curpos;e.di=1;/初始化为向东临位置移动(即向右)Push(S,e);/将已经周的的放入栈中if(curpos.c=end.c&curpos.r=end.r)/如果找到了 出口则终止，并返回 trueFind=true;return Find;else/在其东临位置上移动，当前步数加一curpos=NextPos(curpos,1);curs

6、tep+;else/当前位置不能通过if(!StackEmpty(S)Pop(S,e);/将已经走过的最近位置弹出，数据保存在e中while(e.di=4&!(StackEmpty(S)/当方向改变一周后仍不能找到可通过的 路径MarkPrint(M,e.seat);/留下不能通过的标记Pop(S,e);/删除站定元素curstep-;/whileif(e.di4)/不能通过则改变方向e.di+;/方向顺时针改变一下Push(S,e);curpos = NextPos(e.seat,e.di);/求下一个节点/if/if/elsewhile(!StackEmpty(S)&!Find);/(!S

7、tackEmpty(S)&!Find);/当栈不为空且没有找到出口return false;/没有找到出口则返回false从入口口到出口的查找的流程图（五）调试分析、测试结果（1）由于是不确定的步骤，采用的是易于操作的链式栈，这 样就不免了时间和空间的浪费。（2）对于设计迷宫，可能会觉得会很繁琐，刚开始也是自己 设计迷宫图，但由于是随机设定迷宫的大小这就需要利用随机数 来设计一个迷宫图。而利用运算则可以解决这个问题，因为在 设置迷宫数组时，1就代表通道，而0就是障碍，随意一个随机 数%2得到的就是0或者1就可以自由设计迷宫了。（3）来利用到进出栈时为计算进出栈的情况，特设定了 curstep来

8、调试程序的执行。那下面就介绍一下设计的迷宫界面情况:C:Users李星运阮*叩瞬把结构设3趴基础类.|叵1云 音 云云 音 云 迷迷入入图输输莒工继 否 请请迷米演迷必请请淤演共是!=L 一一歹歹第第口口柴澳米涣第第米吏口 口入出的的宫宫迷迷去续云入入.泌。0-输输 ogI CS CS 是rrr设计心得体会在知识方面,在设计迷宫时需要用到一些基本的如栈的相关信 息，来解决不能使用递归的问题，递归在使用过程中虽然简介但 不易理解通过栈的使用来加强我们对递归的使用。在对问题的理解上我们通过对相关知识的理解和认识，来解决 一些实际问题。附录Stack.h#include #include typed

9、ef struct (int r;int c;PosType;typedef struct(int step;当前位置在路径上的序号PosType seat; /当前位置的坐标int di;彳主下一坐标的方向ElemType;typedef struct NodeType(ElemType data;NodeType *next;*NodeLink;typedef struct(NodeLink top;/指 向栈顶int size;Stack;/栈的基本操作void InitStack(Stack &S)(/初始化栈，设S为空栈S.size=0;/cout栈初始化成功data=e;p-nex

10、t=S.top;S.top=p;S.size+;return true;bool Pop(Stack &S,ElemType &e)/若栈不空，将栈S的栈顶元素删除并由e带回其值，且返回trueNodeType *p=S.top;if(p=NULL)coutdata;S.size-;S.top=p-next;free(p);return true;bool StackTraveser(Stack S)NodeType *p;p=S.top;if(p=NULL)return false;while(!p)coutdata.dinext;return true;主程序#include#includ

11、e #include #include stack.h#include/* 迷宫的相关信息*/ #define Rangle 100typedef struct(int Col,Row;/int arrRangleRangle; /0表示障碍，1表示是可走的通道，-1表示外界的围墙/2表示已经走过，3表示已经知道其不能通过 MazeType;void InitMaze(MazeType &M,int col,int row)/按照用户的输入的行数row和列数col列的二维数组(元素值为1或0)设置迷宫的错初值，加上边缘的一圈的值M.Col=col;M.Row=row;int i;/根据随机产生

12、数进行初始化这个二维数组for(i=1;iM.Row+2;i+)for(int j=1;jM.Col+2;j+)/srand(time(0);int n=rand()%101+100;M.arrij=n%2;/得到的值是1或者0，即恰好是路或是通道围墙的标记for(i=0;iM.Col+2;i+)M.arr0i=-1;M.arrM.Row+1i=-1;for(i=0;iM.Row+2;i+)M.arri0=-1;M.arriM.Col+1=-1;void PrintMaze(MazeType M)/根据已经进行二维数组的标记值来输出迷宫(或者其通路)int i,j;for(i = 0; i M

13、.Row+2; i+) for(j = 0; j M.Col+2; j+)if(M.arrij = 0)coutB;碍，在Dos界面上是白色的else if(M.arrij =-1)cout浓”;围墙else if(M.arrij =2)cout。；elsecout;coutn;bool Pass(MazeType M,PosType pos)/若在迷宫M中，当前位置pos不是障碍物0,不是围墙-1,以前没有经过2且不是不可通 过3 则可以通过，并返回trueif(M.arrpos.rpos.c!=0&M.arrpos.rpos.c!=-1&M.arrpos.rpos.c!=2&M.arrpo

14、s.rpos.c!=2&M.arrpos.rpos.c!=3)return true;else return false;void FootPrint(MazeType &M,PosType pos)/在迷宫中的pos的位置留下足迹，证明已经经过这个位置M.arrpos.rpos.c=2;void MarkPrint(MazeType &M,PosType pos)/在迷宫的pos位置，留下不能通过的标记M.arrpos.rpos.c=3;PosType NextPos(PosType CurPos, int Dir) /根据不同的方向来进行移动PosType ReturnPos;switch

15、 (Dir) (case 1:/向右ReturnPos.r=CurPos.r;ReturnPos.c=CurPos.c+1;break;case 2:/向下ReturnPos.r=CurPos.r+1;ReturnPos.c=CurPos.c;break;case 3:/向左ReturnPos.r=CurPos.r;ReturnPos.c=CurPos.c-1;break;case 4:/向上ReturnPos.r=CurPos.r-1;ReturnPos.c=CurPos.c;break;return ReturnPos;bool MazePath(MazeType &M,PosType s

16、tart,PosType end)求解迷宫M中，从Start到end的一条路径/若存在则返回true，否则返回falseStack S;InitStack(S);PosType curpos=start;/设置当前坐标为入口位置；int curstep=1;当前的步数bool Find=false;是否找到出口ElemType e;doif(Pass(M,curpos)/如果当前位置可以通过(不是障碍物且未曾留下足迹)FootPrint(M,curpos);/在 当前位置标记为 2 e.step=1;e.seat=curpos;e.di=1;/初始化为向东临位置移动（即向右）Push(S,e)

17、;/将已经周的的放入栈中if(curpos.c=end.c&curpos.r=end.r)/如果找到了 出口则终止，并返回 trueFind=true;return Find;else/在其东临位置上移动，当前步数加一curpos=NextPos(curpos,1);curstep+;else/当前位置不能通过if(!StackEmpty(S)Pop(S,e);/将已经走过的最近位置弹出，数据保存在e中while(e.di=4&!(StackEmpty(S)/当方向改变一周后仍不能找到可通过的路径MarkPrint(M,e.seat);/留下不能通过的标记Pop(S,e);/删除站定元素cur

18、step-;/whileif(e.di4)/不能通过则改变方向e.di+;/方向顺时针改变一下Push(S,e);curpos = NextPos(e.seat,e.di);/求下一个节点/if/if/elsewhile(!StackEmpty(S)&!Find);/(!StackEmpty(S)&!Find);/当栈不为空且没有找到出口return false;/没有找到出口则返回falsevoid main()MazeType M;int col,row;PosType start,end;loop:coutrow;coutcol;InitMaze(M,col,row);cout”迷宫图：n;PrintMaze(M);coutstart.rstart.c;coutend.rend.c;if