数据结构迷宫求解

1、【完成题目 3】迷宫求解【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d) 的形式输出，其中 (i,j) 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 【算法设计】本实验的目的是设计一个程序，实现手动或者自动生成一个nxm矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个nxm的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通

2、路，“1”为障碍，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、 下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“”代表“1”，用“”代表“ 0”，用代表行走迷宫的路径。输出迷宫原型图、迷宫路线图 以及迷宫行走路径。如果迷宫为死迷宫，输出信息。可以二维数组存储迷宫数据， 用户指定入口下标和出口下标。 为处理方便起见， 可在迷 宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。?本程序包含三个模块1) 主程序模块：void main()初始化 ;do 接受命令 ;处理命令 ; while (命令 ! = 退出 );2) 栈模块实现栈

3、抽象数据类型；3) 迷宫模块实现迷宫抽象数据类型。【源代码】#include<stdlib.h> / 库中包含 system("pause") 和 rand() 函数#include<stdio.h> /c 语言里的库#include<iostream>#include <malloc.h> #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define M 49#define N

4、 49using namespace std;int mazeMN;typedef int Status;typedef structint m,n,direc;MazeType,*LMazeType;typedef structLMazeType top;LMazeType base;int stacksize;int over;Stack;void Init_hand_Maze(int mazeMN,int m,int n)int i,j;for(i=1;i<=m+1;i+)for(j=1;j<=n+1;j+)mazeij=1;cout<<" 请按行输入迷

5、宫， 0 表示通路， 1 表示障碍 :"<<endl;for(i=1;i<m+1;i+)for(j=1;j<n+1;j+)cin>>mazeij;for(i=1;i<m+1;i+)for(j=1;j<n+1;j+)if(mazeij!=0&&mazeij!=1) cout<<" 您输入有误，请重新输入 "Init_hand_Maze(maze,m,n);/自动生成迷宫void Init_automatic_Maze(int mazeMN,int m,int n)int i,j;cout&l

6、t;v"n 迷宫生成中nn"system("pause");for(i=1;ivm+1;i+)for(j=1;jvn+1;j+)mazeij=rand()%2;/随机生成 0、1void PrintMaze(int mazeMN,int row,int col)int i,j;coutvv" 迷宫如图所示 ."vvendl;for(i=1;ivrow+1;i+)for(j=1;jvcol+1;j+)if(mazeij=1)coutvv""elsecoutvv""coutvvendl;Status

7、 InitStack(Stack &S)S.base=(LMazeType)malloc(STACK_INIT_SIZE * sizeof(MazeType); if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.over=0;return OK;Status Push(Stack &S,MazeType e)if(S.top-S.base>=S.stacksize)S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT)

8、 * sizeof(MazeType); if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(Stack &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 可

9、通， 1 不可通， 2 为已走过Push(S,e); mazee.me.n=2; if(e.m=m&&e.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.base&&S.over!=1)switch(e.direc) /回到上一位置并同时改变方向走下一步case 0:e.n-;e.m+;e.direc=1; break;case 1:e.m-;e.n-;e.di

10、rec=2; break;case 2:e.n+; e.m-;e.direc=3;break;case 3:Pop(S,e);break;while(S.top!=S.base&&S.over!=1);return OK;int PrintPath(Stack S,int mazeMN,int row,int col)if(S.top=S.base) cout<<"n=n" cout<<" 此迷宫无解 nn"return ERROR;MazeType e;while(S.top!=S.base)Pop(S,e);

11、mazee.me.n=(e.direc+10);cout<<" 完成 !"<<endl;cout<<"n=n" cout<<" 路径为 :"<<endl;int i,j;for(i=1;i<row+1;i+)for(j=1;j<col+1;j+)switch(mazeij)case 0:cout<<" "break;case 1:cout<<" "break;case 2:cout<<&q

12、uot; "break;case 10:coutvv"T"break;case 11:coutvv"J "break;case 12:coutvv"J"break;case 13:coutvv"T "；break;coutvvendl;coutvv" 入口 "vvendl;coutvv" 完成 !"vvendl;return OK;int main()int i,m,n,mazeMN,cycle=0;while(cycle!=(-1)coutvv"I*n&

13、quot;coutvv"欢迎进入迷宫求解系统 n"coutvvendl;coutvv"coutvv" 1手动生成迷宫n"coutvv" 2自动生成迷宫n"coutvv" 3退出 nn"coutvv"coutvv"n"coutvv" 请选择你的操作： n"cin>>i;switch(i)case 1:coutvv"n 请输入行数： cin>>m;cout<<"n"cout<<&qu

14、ot; 请输入列数： "cin>>n;while(m<1|m>49)|(n<1|n>49)nn"cout<<"n 抱歉，你输入的行列数超出预设范围 (1-49,1-49), 请重新输入： cout<<"n 请输入行数： "cin>>m;cout<<"n"cout<<" 请输入列数： "cin>>n;Init_hand_Maze(maze,m,n);PrintMaze(maze,m,n);MazeTy

15、pe start,end;cout<<" 请输入起点 m n:"<<endl;cin>>start.m>>start.n;start.direc=0;cout<<" 请输入终点 m n:"<<endl;cin>>end.m>>end.n;Stack S;cout<<" 寻找路径 ."<<endl;InitStack(S);MazePath(S,start,maze,end.m,end.n);PrintPath(S,m

16、aze,m,n);system("pause"); cout<<"nnPress Enter Contiue!n"getchar();否则一直执行while(getchar()!='n'); / 接受一个输入，当为回车时执行 break 跳出， 接受数据break;case 2:cout<<"n 请输入行数： "cin>>m;cout<<"n"cout<<" 请输入列数： "cin>>n;while(m<

17、;0|m>49)|(n<0|n>49)nn"cout<<"n 抱歉，你输入的行列数超出预设范围 (0-49,0-49), 请重新输入： cout<<"n 请输入行数： "cin>>m;cout<<"n"cout<<" 请输入列数： cin>>n;Init_automatic_Maze(maze,m,n);PrintMaze(maze,m,n);cout<<" 请输入起点 m n:"<<endl

18、;cin>>start.m>>start.n;start.direc=0;cout<<" 请输入终点 m n:"<<endl; cin>>end.m>>end.n;cout<<" 寻找路径 ."<<endl;InitStack(S);MazePath(S,start,maze,end.m,end.n);PrintPath(S,maze,m,n);system("pause");cout<<"nnPress Enter Contiue!n" getchar();while(getchar()!='n');break;case 3:cycle=(-1);break;default:cout<<"n"cout<<&q