数据结构-迷宫求解

【完成主题3】迷宫求解【问题的说明】m*n的长方阵表示迷宫，0和1表示迷宫中的通道和障碍。 设计程序，对任意设定的迷宫，求出从入口到出口的通道，或者得出没有通道的结论。【基本要求】首先实现堆栈类型，制作解迷宫的非递归程序。 所获得的路径被输出为三元组(I，j，d )。 其中(I，j )表示迷宫的一个坐标，d表示朝向下一个坐标的方向。【算法设计】本实验的目的是设计手动或自动生成nm矩阵迷宫，寻找从入口到出口的路径的程序。 将其简化为具体实验内容，如下所示选择手动或自动生成nm迷宫，迷宫的左上角作为入口，右下角作为出口，不能通过“0”作为通道，“1”作为障碍。 从出发点开始，目的是右下的终点，可以向上、下、左、右、左上、左下、右上、右下的8个方向行走。 迷宫通过时用“”表示“1”，”表示“0”，然后用“”表示走迷宫的路径。 输出迷宫的原型图，迷宫的路线图，迷宫的行走路线。 迷宫如果是死了的迷宫，就输出信息。可以二维排列存储迷宫数据，用户指定入口下标和出口下标。 为了方便处理，可以在迷宫周围加上障碍。 迷宫的每个位置都有东、南、西、北四个方向相通。该计划包括三个模块1 )主模块：void main ()装模作样初始化do 12222222222222222226接到命令处理指令 while (命令！=退出以下称为2 )栈模块实现栈抽象数据类型3 )迷宫模块实现迷宫抽象数据类型。【源代码】#include /库包含system(pause )和rand ()函数#include /c语言库#include#include#define OK 1定义错误0定义堆栈_ init _ size 100定义堆栈增量10定义溢出- 1#define M 49战斗机#define N 49战斗机使用名称空间STD；int mazeMN；typedef int Status；typedef struct装模作样int m，n，direc；MazeType，*LMazeType；typedef struct装模作样LMazeType top；LMazeType base；堆叠大小；int over；堆栈；void init _ hand _ maze (int maze m n 、intm、int n )装模作样int i，j；for(i=1； i=m 1； I )for(j=1； j=n 1； j )装模作样mazeij=1；以下称为cout 逐行输入迷宫，0为通道，1为故障：mazeij；for(i=1； I=s .堆叠大小)装模作样s.base=(lmaz etype ) realloc (s.base，(s.stacksizestackincrement ) * sizeof (maze type ) )if！ S.base)exit(OVERFLOW )S.top=S.base S.stacksize；堆叠大小=堆叠增量；以下称为*S.top =e；return OK；以下称为status pop (堆栈s，MazeType e )装模作样if(S.top=S.base)return ERROR；e=*-S.top；return OK；以下称为Status MazePath(Stack S，MazeType e，int mazeMN，int m，int n )装模作样do装模作样if(mazee.me.n=0)/0可通过、1不可通过、2可通过装模作样推(s，e )mazee.me.n=2；if(e.m=me.n=n )装模作样S.over=1；/表示一条路径已满return OK；以下称为else e.n；e.direc=0； /来到此点时的方向为0右1下2左3上MazePath(S，e，maze，m，n )以下称为以下称为else装模作样if(S.top！=S.baseS.over！=1)装模作样switch(e.direc) /返回到上一个位置，一边改变方向一边进行下一步装模作样case 0:e.n-；e.m；e.direc=1；break；case 1:e.m-；e.n-；e.direc=2；break；case 2:e.n；e.m-；e.direc=3；break；case 3:Pop(S，e )break；以下称为以下称为以下称为while(S.top！=S.baseS.over！=1；return OK；以下称为int print path (堆栈s，int mazeMN，int row，int col )装模作样if(S.top=S.base )装模作样cout n=n ；cout 这个迷宫解不开nn