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

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

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

3、f struct Lin kNodeelemtype data;數(shù)據(jù)域struct Li nkNode *n ext;/ 指針域Li nkNode;（3）定義鏈棧的頭指針typedef structLi nkNode *top;/棧的頭指針Li nkStack;（4）移動數(shù)組結(jié)構(gòu)的定義typedef structint x,y;/x 為行標(biāo)，y 為列標(biāo)Directio n_in crem;2:算法的設(shè)計：【1】迷宮圖的設(shè)計設(shè)迷宮為 m 行 n 列，利用 mazemn來表示一個迷宮，mazeij=0 或 1;其中：0 表示通路，1 表示不通，當(dāng)從某點向下試探時，中間點有4 個方向可以試探，（見圖

4、）而四個角點有2個方向，其它邊緣點有3 個方向，為使問題簡單化我們用mazem+2n+2來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點的試探方向全部為4，不用再判斷當(dāng)前點的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相一致。假設(shè)有 6 行 8 列的迷宮，如下圖為maze810構(gòu)造的迷宮【2】試探方向的設(shè)計：在上述表示迷宮的情況下，每個點有 4 個方向去試探，如當(dāng)前點的坐標(biāo) （x , y），與其相鄰的 4 個點的坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，如圖2 所示。因為出口在（m，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進(jìn)行。為了簡化問題，方便的求

5、出新點的坐標(biāo)，將從正東開始沿順時針進(jìn)行的這4 個方向（用 0，1, 2，3 表示東、南、西、北）的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move 4 中，在 move 數(shù)組中，每個元素有兩個域組成，x：橫坐標(biāo)增量，y:縱坐標(biāo)增量。Move 數(shù)組如圖 3 所示。move 數(shù)組定義如下：typedef struct int x ;/ 行int y ;列 item ;item move4;這樣對 move 的設(shè)計會很方便地求出從某點（x, y）按某一方向 v （0 v(x , y , d )出棧；求出下一個要試探的方向 d+ ;/當(dāng)遇到死路的時候就出棧，尋找原來點的下一個方向 while(還有剩余試探方向時) i

6、f( d 方向可走)則(x , y , d )入棧;求新點坐標(biāo)(i, j );將新點(i , j)切換為當(dāng)前點(x , y);if ( (x , y )= =( m ,n)結(jié)束；else 重置 d=0 ;else d+ ;五：源程序清單；#i nclude #i nclude int m,n;typedef struct MazeDirectint Dx;int Dy;int direct;MazeDirect;/*定義三元數(shù)組元素的結(jié)構(gòu)*/typedef MazeDirect elemtype;typedef struct Lin kNodeelemtype data;struct Lin

7、kNode *n ext;/*定義鏈表節(jié)點的結(jié)構(gòu)組成*/Li nkNode;typedef structLi nkNode *top;/*定義鏈棧的頭指針*/Lin kStack;void ini_stack(LinkStack *stack)/* 初始化鏈棧 */stack-top=NULL;int empty_Stack(LinkStack *stack)/* 判斷是否為空棧 */if (stack-top!=NULL)return 0;elsereturn 1;void push_Stack(LinkStack *stack,elemtype x)/* 入棧 */Li nkNode *s

8、;s=(L in kNode *)malloc(sizeof(Li nkNode);s-data=x;s-n ext=stack-top;stack-top=s;elemtype pop_Stack(LinkStack *stack) /* 出棧 */ elemtype x;Lin kNode *p;elemtype tmpNull=0,0,0;if (stack-top=NULL)return tmpNull;/(NULL)else x=stack-top-data; p=stack-top;stack-top=p-n ext; free(p);return (x); int size_st

9、ack(L in kStack stack) int i;Li nkNode *Numb;i=0;Numb=stack.top; while(Numb!=NULL) Numb=Numb-n ext; i+;return i; int w,t,maze100100;typedef structint x,y;/x 為行標(biāo)，y 為列標(biāo)Directio nn crem;Directionncrem MazeMove4=0,1,1,0,0,-1,-1,0;typedef MazeDirect TmpType;int Maze_path()MazeDirect tmp,path;Lin kStack s

10、;int x,y,Px,Py,d,flag=O;/*棧的規(guī)模大小*/in i_stack (& s);tmp.Dx=1;tmp.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; 遇到死路的時候，回溯(通過出棧完成)while (d4)Px=x+MazeMoved.x;Py=y+MazeMoved.y;if (mazePxPy=O)tmp.Dx=x;tmp.Dy=y;tmp.direc

11、t=d;push_Stack (&s,tmp);x=Px;y=Py;maze x y=-1;/* 標(biāo)記，防止重復(fù)點 */ if(x=m&y=n)flag=1;printf(n 到達(dá)迷宮出口：d,%d,x,y);printf(n 經(jīng)過的節(jié)點有：%d 個,size_stack(s);while(!empty_Stack( &s)path=pop_Stack (&s);prin tf(n(%d,%d,%d),path.Dx,path.Dy,path.direct);break;else d=0;結(jié)束 ifelse d+;/結(jié)束內(nèi)部 while/結(jié)束外部 whilereturn flag;void mai n()printf(”請輸入迷宮圖的行數(shù)和列數(shù)(輸入格式為 i,j)