堆棧迷宮求解

堆棧迷宮求解#include<iostream>#include<malloc.h>#include<cstdlib>//隨機數(shù)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三個數(shù)if(k)arry[i][j]=0;else{if((i==1&&j==1)||(i==N-2&&j==N-2))//距入口或出口一步的路是必經(jīng)之路，故設該通道塊為“ 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;}//迷宮函數(shù)//若迷宮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說明 :■不能走的區(qū)域 \t

走不通的區(qū)域 ";cout<<"\n“空格”代表未到過的區(qū)域";cout<<"\n○代表能通過的路徑，指向終點";cout<<"\n 命令菜單 ";cout<<"\n1.系統(tǒng)隨機生成一個迷宮 ";cout<<"\n2.輸入一個迷宮 ";cout<<"\n3.打印走出迷宮的路徑 ";cout<<"\n4.退出游戲 ";cout<<"\n============================================";cout<<"\n請輸入您想執(zhí)行的操作命令： "<<endl;intn;while(cin>>n&&n){if(n==1)cout<<"系統(tǒng)將默認生成一個大小為"<<N<<"x"<<N<<"的迷宮:"<<endl;Random();MazePath(arry[N][N],start,end,S);PrintMaze();system("pause");cout<<"請輸入您接下來要執(zhí)行的操作命令："<<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<<"請輸入您接下來要執(zhí)