利用棧實(shí)現(xiàn)迷宮的求解

1、利用棧實(shí)現(xiàn)迷宮的求解一、要解決的問題：以一個(gè)m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙，設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。二：算法基本思想描述:用一個(gè)字符類型的二維數(shù)組表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的邊界；第1行第1列元素和第m行第n列元素置成“0”， 表示迷宮的入口和出口走迷宮的過程可以模擬為一個(gè)搜索的過程：每到一處，總讓它按東、南、西、北4個(gè)方向順序試探下一個(gè)位置；用二維數(shù)組move記錄4個(gè)方向上行下標(biāo)增量和列下標(biāo)增

2、量，則沿第i個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用move數(shù)組確定： Px=x+movei0 Py=y+movei1如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果4個(gè)方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上繼續(xù)試探下一位置。三：設(shè)計(jì)：1：數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：（1）定義三元數(shù)組元素的結(jié)構(gòu)typedef struct MazeDirect int Dx; /行標(biāo) int Dy; /列標(biāo) int direct; /走到下一個(gè)坐標(biāo)點(diǎn)的方向MazeDirect; （2）定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)組成typedef struct LinkNode elemtype data

3、; /數(shù)據(jù)域 struct LinkNode *next; /指針域LinkNode;（3）定義鏈棧的頭指針typedef struct LinkNode *top; /棧的頭指針LinkStack;（4）移動數(shù)組結(jié)構(gòu)的定義typedef struct int x,y;/x為行標(biāo)，y為列標(biāo)Direction_increm;2：算法的設(shè)計(jì)：【1】迷宮圖的設(shè)計(jì)設(shè)迷宮為m行n列，利用mazemn來表示一個(gè)迷宮，mazeij=0或1; 其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有4個(gè)方向可以試探，（見圖）而四個(gè)角點(diǎn)有2個(gè)方向，其它邊緣點(diǎn)有3個(gè)方向，為使問題簡單化我們用mazem+2n+2

4、來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個(gè)點(diǎn)的試探方向全部為4，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)，同時(shí)與迷宮周圍是墻壁這一實(shí)際問題相一致。假設(shè)有6行8列的迷宮，如下圖為maze810構(gòu)造的迷宮1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1【2】試探方向的設(shè)計(jì)：在上述表示迷宮的情況下，每個(gè)點(diǎn)有4個(gè)方向去試探，

5、如當(dāng)前點(diǎn)的坐標(biāo)(x , y)，與其相鄰的4個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，如圖2所示。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針方向進(jìn)行。為了簡化問題，方便的求出新點(diǎn)的坐標(biāo)，將從正東開始沿順時(shí)針進(jìn)行的這4個(gè)方向（用0，1，2，3表示東、南、西、北）的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組move 4 中，在move 數(shù)組中，每個(gè)元素有兩個(gè)域組成，x：橫坐標(biāo)增量，y：縱坐標(biāo)增量。Move數(shù)組如圖3所示。move數(shù)組定義如下：typedef struct int x ; /行int y ; /列 item ; item move4 ;這樣對move的設(shè)計(jì)會很方便

6、地求出從某點(diǎn) (x，y) 按某一方向 v (0v3) 到達(dá)的新點(diǎn)（i，j）的坐標(biāo)：i =x + movev.x ，j = y + movev.y 。(x，y)圖2 與點(diǎn)(x，y)相鄰的4個(gè)點(diǎn)及坐標(biāo)(x，y+1)(x，y-1)(x+1，y)(x-1，y)xy00111020-13-10圖3 增量數(shù)組move【3】棧的設(shè)計(jì)：當(dāng)?shù)竭_(dá)了某點(diǎn)而無路可走時(shí)需返回前一點(diǎn)，再從前一點(diǎn)開始向下一個(gè)方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向，即每走一步棧中記下的內(nèi)容為(行，列，來的方向)。對于圖1所示迷宮，依次入棧為：top 3,4,0 3,3,0 3,2,1 2,

7、2,0 2,1,1 1,1,0棧中每一組數(shù)據(jù)是所到達(dá)的每點(diǎn)的坐標(biāo)及從該點(diǎn)沿哪個(gè)方向向下走的，對于圖3迷宮，走的路線為：(1,1,0)(2,1,1)(2,2,0)(3,2,1)(3,3,0)(3,4,0)（下腳標(biāo)表示方向），當(dāng)無路可走，則應(yīng)回溯，對應(yīng)的操作是出棧，沿下一個(gè)方向即方向繼續(xù)試探。棧中元素是一個(gè)由行、列、方向組成的三元組，棧元素的設(shè)計(jì)如下：typedef structint x , y , d ;/* 橫縱坐標(biāo)及方向*/datatype ;棧的定義為： SeqStack s ;【4】. 如何防止重復(fù)到達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個(gè)標(biāo)志數(shù)組markmn，它的所有元素都初

8、始化為0，一旦到達(dá)了某一點(diǎn) ( i , j )之后，使mark i j 置1，下次再試探這個(gè)位置時(shí)就不能再走了。另一種方法是當(dāng)?shù)竭_(dá)某點(diǎn)（i , j）后使maze i j 置 -1，以便區(qū)別未到達(dá)過的點(diǎn)，同樣也能起到防止走重復(fù)點(diǎn)的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。四：詳細(xì)設(shè)計(jì)；1. 算法的設(shè)計(jì)思想及流程圖（1）主要函數(shù)的功能說明 void ini_stack(LinkStack *)/*初始化鏈棧*/ int empty_Stack(LinkStack *)/*判斷是否為空棧*/ void push_Stack(LinkStack *,elemtype)/*入棧*/ elemtyp

9、e pop_Stack(LinkStack *) /*出棧*/ int size_stack(LinkStack ) /*棧的規(guī)模大小*/ （2） 算法描述【偽代碼描述】迷宮求解算法思想如下：(1) 棧初始化;(2) 將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為-1）入棧(3) while (棧不空) 棧頂元素（x , y , d）出棧 ;求出下一個(gè)要試探的方向d+ ;/當(dāng)遇到死路的時(shí)候就出棧，尋找原來點(diǎn)的下一個(gè)方向 while （還有剩余試探方向時(shí)） if （d方向可走）則 （x , y , d）入棧 ; 求新點(diǎn)坐標(biāo) (i, j ) ;將新點(diǎn)（i , j）切換為當(dāng)前點(diǎn)（x , y） ; if ( (x

10、 ,)= =(,n) ) 結(jié)束 ; else 重置 d=0 ; else d+ ; 五：源程序清單；#include #include int m,n;typedef struct MazeDirect int Dx; int Dy; int direct;MazeDirect; /*定義三元數(shù)組元素的結(jié)構(gòu)*/typedef MazeDirect elemtype;typedef struct LinkNode elemtype data; struct LinkNode *next; /*定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)組成*/LinkNode;typedef struct LinkNode *top;

11、/*定義鏈棧的頭指針*/LinkStack;void ini_stack(LinkStack *stack)/*初始化鏈棧*/ stack-top=NULL;int empty_Stack(LinkStack *stack)/*判斷是否為空棧*/ if (stack-top!=NULL) return 0; else return 1;void push_Stack(LinkStack *stack,elemtype x)/*入棧*/ LinkNode *s; s=(LinkNode *)malloc(sizeof(LinkNode); s-data=x; s-next=stack-top;

12、stack-top=s;elemtype pop_Stack(LinkStack *stack) /*出棧*/ elemtype x; LinkNode *p; elemtype tmpNull=0,0,0; if (stack-top=NULL) return tmpNull;/(NULL) else x=stack-top-data; p=stack-top; stack-top=p-next; free(p); return (x); int size_stack(LinkStack stack) /*棧的規(guī)模大小*/ int i; LinkNode *Numb; i=0; Numb=s

13、tack.top; while(Numb!=NULL) Numb=Numb-next; i+; return i;int w,t,maze100100;typedef struct int x,y;/x為行標(biāo)，y為列標(biāo)Direction_increm;Direction_increm MazeMove4=0,1,1,0, 0,-1,-1,0;typedef MazeDirect TmpType;int Maze_path() MazeDirect tmp,path; LinkStack s; int x,y,Px,Py,d,flag=0; ini_stack(&s); tmp.Dx=1;tmp

14、.Dy=1;tmp.direct=-1; push_Stack(&s,tmp); while (!empty_Stack(&s) tmp=pop_Stack(&s); x=tmp.Dx;y=tmp.Dy;d=tmp.direct+1;/遇到死路的時(shí)候，回溯（通過出棧完成） while (d4) Px=x+MazeMoved.x; Py=y+MazeMoved.y; if (mazePxPy=0) tmp.Dx=x; tmp.Dy=y; tmp.direct=d; push_Stack(&s,tmp); x=Px;y=Py;mazexy=-1;/*標(biāo)記，防止重復(fù)點(diǎn)*/ if(x=m&y=n) flag=1; printf(n到達(dá)迷宮出口：%d,%d,x,y); printf(n經(jīng)過的節(jié)點(diǎn)有：%d個(gè),size_stack(s); while(!empty_Stack(&s) path=pop_Stack(&s); printf(n(%d,%d,%d),path.Dx,path.Dy,path.direct); break; else d=0; /結(jié)束if else d+; /結(jié)束內(nèi)部w