迷宮問(wèn)題的求解

迷宮問(wèn)題求解問(wèn)題描述：請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法實(shí)現(xiàn)迷宮問(wèn)題求解。需求分析：程序可實(shí)現(xiàn)用戶與計(jì)算機(jī)的交互過(guò)程。在計(jì)算機(jī)顯示提示信息后，可由用戶輸入迷宮的大小與形態(tài)，以“0”表示墻壁，以“1”表示通路。利用棧操作尋找一條從入口至出口的通路，最終輸出帶有路線的迷宮。二算法思想： ■.?棧的設(shè)計(jì)：用計(jì)算機(jī)解迷宮問(wèn)題時(shí)，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通則繼續(xù)向前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。因此，可以利用“?！眮?lái)求解迷宮問(wèn)題。表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用maze[m][n]來(lái)表示一個(gè)迷宮，maze[i][j]=0或1;其中0表示墻壁（不通），1表示通路，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有4個(gè)方向可以試探，（見(jiàn)圖）而四個(gè)角點(diǎn)有2個(gè)方向，其它邊緣點(diǎn)有3個(gè)方向，為使問(wèn)題簡(jiǎn)單化，用maze[m+2][n+2]來(lái)表示迷宮，而迷宮的四周的值全部為0。這樣做可使問(wèn)題簡(jiǎn)化，每個(gè)點(diǎn)的試探方向全部為4,不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)，同時(shí)與迷宮周圍是墻壁這一實(shí)際問(wèn)題相一致。00123456789-0000000000101000100002011010000030111111100401100100005001110111060100111110700000000001試探方向：在上述表示迷宮的情況下，每個(gè)點(diǎn)有4個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)（x,y），與其相鄰的4個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，如圖所示。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針?lè)较蜻M(jìn)行。為了簡(jiǎn)化問(wèn)題，方便的求出新點(diǎn)的坐標(biāo)，將從正東開(kāi)始沿順時(shí)針進(jìn)行的這4個(gè)方向(用0,1,2,3表示東、南、西、北)的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組direct[4]中，在該數(shù)組中，每個(gè)元素有兩個(gè)域組成，x成，x：橫坐標(biāo)增量，y：縱坐標(biāo)增量。Xy001 1I1o120'-13-10增量數(shù)組direct增量數(shù)組direct(翼，y-1) (X,V) 4 y+1)1F(E,y)與點(diǎn)(跖病睥的4個(gè)點(diǎn)及坐標(biāo)防止重復(fù)到達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)：定義“足跡”函數(shù)，在到達(dá)某點(diǎn)(i,j)后將使maze[i][j]置為-1，以便區(qū)別未到達(dá)過(guò)的點(diǎn)，起到防止走重復(fù)點(diǎn)的目的。概要設(shè)計(jì)：1.棧的抽象數(shù)據(jù)類型的定義：ADTStack{數(shù)據(jù)對(duì)象：D={ai|aiEElemSet,i=1,2,...n,nN0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1ED,i=1,2,...n}基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回1，否則返回0。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}ADTStack2.迷宮部分的函數(shù)功能:Pass(b)當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，返回1,否則返回0。FootPrint(a)使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curstep),表示經(jīng)過(guò)。NextPos(c，di)根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置。MarkPrint(b)使迷宮m的b點(diǎn)的序號(hào)變?yōu)?1(不能通過(guò)的路徑)。MazePath(start，end)若迷宮maze中存在從入口start到出口end的通道，則求得一條。Print(x，y)輸出迷宮。程序代碼：#include<iostream.h>#include<iomanip.h>#include<malloc.h>#include<process.h>#defineMAXLENGTH15〃設(shè)迷宮的最大行列數(shù)為15typedefintMazeType[MAXLENGTH][MAXLENGTH];〃迷宮數(shù)組[行][列]typedefstruct{〃迷宮坐標(biāo)位置類型intx; 〃行值inty; 〃列值}PosType;typedefstruct{〃棧的元素類型intord; 〃通道塊在路徑上的“序號(hào)”PosTypeseat; 〃通道塊在迷宮中的“坐標(biāo)位置"intdi; 〃從此通道塊走向下一通道塊的“方向”(0?3表示東?北)}SElemType;MazeTypem; 〃迷宮數(shù)組intcurstep=1; 〃當(dāng)前足跡,初值為1//*****************棧的定義““““““““““““““““““小小小小小小小小小小小小小小小小小小#defineSTACK_INIT_SIZE10//存儲(chǔ)空間初始分配量#defineSTACKINCREMENT2//存儲(chǔ)空間分配增量typedefstructSqStack{//順序棧SElemType*base; //在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType*top; //棧頂指針intstacksize;//當(dāng)前已分配的存儲(chǔ)空間，以元素為單位}SqStack;intInitStack(SqStack*S){//構(gòu)造一個(gè)空棧S//為棧底分配一個(gè)指定大小的存儲(chǔ)空間(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(0);(*S).top=(*S).base;//棧底與棧頂相同表示一個(gè)空棧(*S).stacksize=STACK_INIT_SIZE;return1;}intStackEmpty(SqStackS){//若棧S為空棧(棧頂與棧底相同的)，則返回1，否則返回0if(S.top==S.base)return1;elsereturn0;}intPush(SqStack*S,SElemTypee){//插入元素e為新的棧頂元素if((*S).top-(*S).base>=(*S).stacksize) 〃棧滿，追加存儲(chǔ)空間{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(0);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;return1;}intPop(SqStack*S,SElemType*e){//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0if((*S).top==(*S).base)return0;*e=*--(*S).top;return1;}“““““““““““““““““““小小小小小小小小小小小小小小小小小小小〃*****************迷宮部分的定義“““““““““““““““““““小小小小小小小小小小小小小小小小小小小//定義墻元素值為0,可通過(guò)路徑為1,不能通過(guò)路徑為-1，通過(guò)路徑為足跡intPass(PosTypeb){//當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，return1;否則，return0if(m[b.x][b.y]==1)return1;elsereturn0;}voidFootPrint(PosTypea){//使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curstep)，表示經(jīng)過(guò)m[a.x][a.y]=curstep;}PosTypeNextPos(PosTypec,intdi){//根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}}; //{行增量，列增量}//移動(dòng)方向，依次為東南西北c.x+=direc[di].x;c.y+=direc[di].y;returnc;voidMarkPrint(PosTypeb){//使迷宮m的b點(diǎn)的序號(hào)變?yōu)?1(不能通過(guò)的路徑)m[b.x][b.y]=-1;}intMazePath(PosTypestart,PosTypeend){〃若迷宮maze中存在從入口start到出口end的通道，則求得一條〃存放在棧中(從棧底到棧頂)，并返回1；否則返回0SqStackS;PosTypecurpos;SElemTypee;InitStack(&S);curpos=start;do{if(Pass(curpos)){//當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊FootPrint(curpos);〃留下足跡e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); //入棧當(dāng)前位置及狀態(tài)curstep++; 〃足跡加1if(curpos.x==end.x&&curpos.y==end.y)//到達(dá)終點(diǎn)(出口)return1;curpos=NextPos(curpos,e.di);}else{//當(dāng)前位置不能通過(guò)if(!StackEmpty(S)){Pop(&S,&e);//退棧到前一位置curstep--;

〃前一位置處于最后一個(gè)方向(北)while(e.di==3&&!StackEmpty(S)){MarkPrint(e.seat);//留下不能通過(guò)的標(biāo)記(-1)Pop(&S,&e); 〃退回一步curstep--;}if(e.di<3) 〃若沒(méi)到最后一個(gè)方向(北){e.di++; 〃換下一個(gè)方向探索Push(&S,e);curstep++;〃設(shè)定當(dāng)前位置是該新方向上的相鄰塊curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));return0;}voidPrint(intx,inty){〃輸出迷宮inti,j;for(i=0;i<x;i++){for(j=0;j<y;j++)cout<<setw(3)<<m[i][j];cout<<endl;}}〃*****************主程序部分〃*****************主程序部分““““““““““““““““““小小小小小小小小小小小小小小小小小小intmain(){PosTypebegin,end;inti,j,x,y,x1,y1;coutvv"************MAZETESTFILE************"vvendlvvendl;cout?"請(qǐng)輸入迷宮的總行列數(shù)（包括外墻）：（空格隔開(kāi)）”；cin?x?y;for(i=0;ivx;i++) 〃定義周邊值為0(同墻){m[0][i]=0; 〃迷宮上面行的周邊即上邊墻m[x-l][i]=0; 〃迷宮下面行的周邊即下邊墻}for(j=l;j<y-l;j++){m[j][0]=0; 〃迷宮左邊列的周邊即左邊墻m(j][y-i]=o； 〃迷宮右邊列的周邊即右邊墻}for(i=l;i<x-l;i++)for(j=l;j<y-l;j++)m[i][j]=l;〃定義通道初值為1cout?endl?"iW輸入迷宮內(nèi)部"墻單元”的個(gè)數(shù)：cin?j;cout?endl?"i#依次輸入迷宮內(nèi)部每個(gè)“墻單元”的行數(shù)，列數(shù)：(空格隔開(kāi))"?endl;for(i=l;iv=j;i++){cin?xl?yl;m[xl][yl]=0; 〃定義墻的值為0}cout?endl?"迷宮結(jié)構(gòu)如下："vvendl;Print(x,y);begin.x=l;begin.y=l;end.x=x-2;end.y=y-2; 〃定義起點(diǎn)與終點(diǎn)位置

if(MazePath(begin,end)){//求得一條通路cout<<endl<<"此迷宮從入口到出口的一條路徑如下:"<<endl;Print(x,y);//輸出此通路}elsecout<<endl<<"此迷宮沒(méi)有從入口到出口的路徑"<<endl;return0;}運(yùn)行結(jié)果：'F:\3-60d就*詹要敏推'桌囪W3^&\Debug\m3ze.eMeMM EETESTFILEXXX**HMIKKNXXX《空格隔開(kāi)>7?“墻單元”的個(gè)數(shù)：8“墻單元”的行數(shù)-列魏(空格隔開(kāi))24121

01000

000101110iii1

01000

000101110iiie1B0765

01

080432

031210110anykeytocontinue輸入迷宮的總行列數(shù)(包括外墻)。現(xiàn)取7行7列方陣(實(shí)際部分6*6)。輸入迷宮內(nèi)部“墻單元”的個(gè)數(shù)。現(xiàn)取8個(gè)，即在6*6方陣中有8個(gè)墻。依次輸入迷宮內(nèi)部每個(gè)墻單元的行列數(shù)?，F(xiàn)取(1,2)(2,4)(3,1)(3,2)(3,3)(4,3)(4,5)(5,3)作

為墻。輸