堆栈迷宫求解

堆栈迷宫求解#include<iostream>#include<malloc.h>#include<cstdlib>//随机数srand头文件#include<time.h>//time头文件defineOK1defineOVERFLOW0defineTRUE1defineFALSE0defineSTACK_INIT_SIZE100//存储空间初始分配量defineSTACKINCREMENT10//存储空间分配增量defineN5usingnamespacestd;typedefstruct{intx,y;}PosType;//定义通道块位置坐标typedefstruct{intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的坐标位置intdi; //从此通道块走向下一通道块的方向}SElemType; //栈的元素类型定义if(!s.base)exit(OVERFLOW);if(!s.base)exit(OVERFLOW);存储分配失败//typedefstruct{SElemType*base;SElemType*top;intstacksize;//当前已分配的存储空间}SqStack;//栈定义intarry[N][N];intRandom(){inti,j,k;srand(unsigned(time(0)));arry[1][0]=arry[N-2][N-1]=0;//将入口、出口设置为“ 0”即可通过for(j=0;j<N;j++)arry[0][j]=arry[N-1][j]=1; //设置迷宫外围“不可走” ，保证只有一个出口和入口for(i=2;i<N-1;i++)arry[i][0]=arry[i-1][N-1]=1; //设置迷宫外围“不可走” ，保证只有一个出口和入口for(i=1;i<N-1;i++)for(j=1;j<N-1;j++){k=rand()%3;//随机生成 0、1、2三个数if(k)arry[i][j]=0;else{if((i==1&&j==1)||(i==N-2&&j==N-2))//距入口或出口一步的路是必经之路，故设该通道块为“ 0”加大迷宫能通行的概率arry[i][j]=0;elsearry[i][j]=1;}}returnOK;}intInitStack(SqStack&s){//构造一个空栈 Ss.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);存储分配失败//s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}intPush(SqStack&s,SElemType&e){插入// e为新的栈顶元素if(s.top-s.base>=STACK_INIT_SIZE)栈满{//,追加存储空间s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}intPop(SqStack&s,SElemType&e){若栈不空，// 删除 S的栈顶元素if(s.base==s.top)returnFALSE;e=*--s.top;returnOK;}PosTypeNextPos(PosType&e,intdir){//探索下一步PosTypeE;switch(dir){case1:E.x=e.x;//向下E.y=e.y+1;break;case2:E.x=e.x+1;//向右E.y=e.y;break;case3:E.x=e.x;//向上returnOVERFLOW;returnOVERFLOW;//其它returnOVERFLOW;returnOVERFLOW;//其它E.y=e.y-1;break;case4:E.x=e.x-1;//向左E.y=e.y;break;}returnE;}intStackEmpty(SqStacks){/判断栈是否为空/if(s.top==s.base)returnOK;returnOVERFLOW;}intMarkPrint(PosTypee){//留下不能通过的足迹arry[e.x][e.y]=3;returnOK;}intPass(PosTypee){/当前块可否通过/if(arry[e.x][e.y]==0)//0时可以通过returnOK;//如果当前位置是可以通过，返回 1if(Pass(curpos))if(Pass(curpos))if(Pass(curpos))if(Pass(curpos))情况返回 0intFootPrint(PosTypee){//留下通过的足迹arry[e.x][e.y]=7;returnOK;}//迷宫函数//若迷宫maze中从入口 start到出口end的通道，则求得一条存放在栈中(从栈底到栈顶) ，并返回 TRUE；否则返回 FALSEintMazePath(intarry,PosTypestart,PosTypeend,SqStack&s){PosTypecurpos;InitStack(s);SElemTypee;intcurstep;curpos=start;//设定"当前位置"为"入口位置"curstep=1;//探索第一步do{}}{//当前位置可通过，即是未曾走到过的通道块FootPrint(curpos);//留下足迹e.di=1;e.ord=curstep;e.seat=curpos;Push(s,e);//加入路径if(curpos.x==end.x&&curpos.y==end.y){cout<<"Goodjob！能到达终点 !"<<endl;returnTRUE;}curpos=NextPos(curpos,1);//下一位置是当前位置的东邻curstep++;//探索下一步}else{//当前位置不能通过if(!StackEmpty(s)){Pop(s,e);while(e.di==4&&!StackEmpty(s)){MarkPrint(e.seat);Pop(s,e);}if(e.di<4){e.di++;Push(s,e);//留下不能通过的标记，并退回一步curpos=NextPos(e.seat,e.di);//当前位置设为新方向的相邻块}}}}while(!StackEmpty(s));cout<<"Sorry!不能到达终点 !"<<endl;returnFALSE;}voidPrintMaze(){//打印迷宫inti,j;for(i=0;i<N;i++){for(j=0;j<N;j++){if(arry[i][j]==0)cout<<"";elseif(arry[i][j]==1)cout<<"■";//迷宫的“墙”elseif(arry[i][j]==3)cout<<"

"; //不通的路elseif(arry[i][j]==7)cout<<"○"; //通过的路径}cout<<endl;}voidmain(){SqStackS;PosTypestart,end;start.x=1;start.y=0;//起点坐标end.x=N-2;end.y=N-1;//终点坐标cout<<"\n==================迷宫游戏==================";cout<<"\n说明 :■不能走的区域 \t

走不通的区域 ";cout<<"\n“空格”代表未到过的区域";cout<<"\n○代表能通过的路径，指向终点";cout<<"\n 命令菜单 ";cout<<"\n1.系统随机生成一个迷宫 ";cout<<"\n2.输入一个迷宫 ";cout<<"\n3.打印走出迷宫的路径 ";cout<<"\n4.退出游戏 ";cout<<"\n============================================";cout<<"\n请输入您想执行的操作命令： "<<endl;intn;while(cin>>n&&n){if(n==1)cout<<"系统将默认生成一个大小为"<<N<<"x"<<N<<"的迷宫:"<<endl;Random();MazePath(arry[N][N],start,end,S);PrintMaze();system("pause");cout<<"请输入您接下来要执行的操作命令："<<endl;}elseif(n==2){cout<<"提示：此迷宫的大小须为"<<N<<"x"<<N<<":"<<endl;cout<<"请输入迷宫： "<<endl;for(inti=0;i<N;i++)for(intj=0;j<N;j++)}}}}cin>>arry[i][j];PosTypes1,e1;cout<<"请输入入口坐标： "<<endl;cin>>s1.x>>s1.y;cout<<"请输入出口坐标： "<<endl;cin>>e1.x>>e1.y;MazePath(arry[N][N],s1,e1,S);PrintMaze();system("pause");cout<<"请输入您接下来要执