3.3迷宫问题

《3.3迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告题目：迷宫问题迷宫四周设为墙；无填充处为可通达处。设每个点有四个可通方向，分别为东南西北。左上角为入口，右下角为出口。迷宫有一个出口，一个入口。设计程序求解迷宫的一条通路。算法：#include#include#defineMaxSize15//定义迷宫的最大行列数为15usingnamespacestd;intMaze[MaxSize][MaxSize];intcurstep=1;structLocate{intx;//横坐标属性xinty;//列坐标属性y};structSElem{intord;Locateseat;intd;//方向属性d

2、(0～3分别表示东南西北)};structSqStack{SElem*base;SElem*top;intstacksize;};intInitStack(SqStack*S){(*S).base=(SElem*)malloc(10*sizeof(SElem));if(!(*S).base)exit(0);(*S).top=(*S).base;(*S).stacksize=10;return1;}intStackEmpty(SqStackS){if(S.top==S.base)return1;elsereturn0;}intPush(SqStack*S,SEleme){if((*S).top

3、-(*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;return1;}intPop(SqStack*S,SElem*e){if((*S).top==(*S).base)return0;*e=*--(*S).top;return1;}intPass(Locateb){if(

4、Maze[b.x][b.y]==0)return1;elsereturn0;}voidFootPrint(Locatea){Maze[a.x][a.y]=curstep;}LocateNextLocate(Locatec,intd){Locatemove[4]={{0,1},{1,0},{0,-1},{-1,0}};//把东南西北依次编号为0、1、2、3放在增量数组move[4]中c.x+=move[d].x;c.y+=move[d].y;returnc;}voidMarkPrint(Locateb){Maze[b.x][b.y]=-1;//定义迷宫不能通过路径为-1}intMazepath

5、(Locatestart,Locateend){SqStackS;Locatecurloc;SEleme;InitStack(&S);curloc=start;do{if(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)//到达出口return1;curloc=NextLocate(curloc,e.d);}else{if(!StackEmpty(S))

6、{Pop(&S,&e);curstep--;while(e.d==3&&!StackEmpty(S)){MarkPrint(e.seat);//不能通过的路径标记为-1Pop(&S,&e);//后退一步curstep--;}if(e.d<3)//若还没向北探索{e.d++;Push(&S,e);curstep++;curloc=NextLocate(e.seat,e.d);}}}}while(!StackEmpty(S));return0;}voidPrintMaze(intx,inty){for(inti=0;i

7、)<>x>>y;for(i=0;i