3.3迷宫问题.docx

实验报告题目：迷宫问题迷宫四周设为墙；无填充处为可通达处。设每个点有四个可通方向，分别为东南西北。左上角为入口，右下角为出口。迷宫有一个出口，一个入口。设计程序求解迷宫的一条通路。算法：#include#include#define MaxSize 15/定义迷宫的最大行列数为15using namespace std;int MazeMaxSizeMaxSize;int curstep=1;struct Locateint x;/横坐标属性xint y;/列坐标属性y;struct SElemint ord;Locate seat;int d;/方向属性d(03分别表示东南西北); struct SqStackSElem *base;SElem *top;int stacksize;int InitStack(SqStack *S)(*S).base=(SElem *)malloc(10*sizeof(SElem);if(!(*S).base)exit(0);(*S).top=(*S).base;(*S).stacksize=10;return 1;int StackEmpty(SqStack S)if(S.top=S.base)return 1;elsereturn 0;int Push(SqStack *S, SElem e)if(*S).top-(*S).base=(*S).stacksize)(*S).base=(SElem *)realloc(*S).base , (*S).stacksize+2)*sizeof(SElem);if(!(*S).base)exit(0);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=2;*(*S).top)+=e;return 1;int Pop(SqStack *S,SElem *e)if(*S).top=(*S).base)return 0;*e=*-(*S).top;return 1;int Pass(Locate b)if(Mazeb.xb.y=0)return 1;elsereturn 0;void FootPrint(Locate a)Mazea.xa.y=curstep;Locate NextLocate(Locate c,int d)Locate move4=0,1,1,0,0,-1,-1,0;/把东南西北依次编号为0、1、2、3放在增量数组move4中c.x+=moved.x;c.y+=moved.y;return c;void MarkPrint(Locate b)Mazeb.xb.y=-1;/定义迷宫不能通过路径为-1 int Mazepath(Locate start,Locate end) SqStack S;Locate curloc;SElem e;InitStack(&S);curloc=start;doif(Pass(curloc)FootPrint(curloc);e.ord=curstep;e.seat.x=curloc.x;e.seat.y=curloc.y;e.d=0;Push(&S,e);curstep+;if(curloc.x=end.x&curloc.y=end.y)/到达出口 return 1;curloc=NextLocate(curloc,e.d);elseif(!StackEmpty(S)Pop(&S,&e);curstep-;while(e.d=3&!StackEmpty(S)MarkPrint(e.seat);/不能通过的路径标记为-1Pop(&S,&e);/后退一步 curstep-;if(e.d3)/若还没向北探索 e.d+;Push(&S,e);curstep+;curloc=NextLocate(e.seat,e.d);while(!StackEmpty(S);return 0; void PrintMaze(int x,int y)for(int i=0;ix;i+)for(int j=0;jy;j+)coutsetw(4)leftMazeij;coutendl;int main()Locate begin,end;int i,j,x,y,x1,y1;coutxy;for(i=0;ix;i+)/定义墙元素值为1Maze0i=1;Mazex-1i=1;for(j=1;jy-1;j+)Mazej0=1; Mazejy-1=1;for(i=1;ix-1;i+)for(j=1;jy-1;j+)Mazeij=0;/定义可通过路径为0coutj;cout请依次输入迷宫内部每个“障碍物”所在的行列数：endl;for(i=1;ix1y1;Mazex1y1=1;/定义墙的值为1cout迷宫结构如下：endl;PrintMaze(x,y);cout请输入起点和终点所在行列数：begin.xbegin.yend.xend.y;/*begin.x=1;begin.y=1;end.x=x-2;end.y=y-2;/定义起点与终点位置*