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

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

2、；用二維數(shù)組 move 記錄 4 個(gè)方向上行下標(biāo)增量和列下標(biāo)增量，則沿第 i 個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用move 數(shù)組確定：Px=x+movei0Py=y+movei1如果某方向可以通過(guò)，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索； 如果 4 個(gè)方向都走不通或曾經(jīng)到達(dá)過(guò)，則退回一步，在原來(lái)的位置上繼續(xù)試探下一位置。三：設(shè)計(jì)：1：數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：（1）定義三元數(shù)組元素的結(jié)構(gòu)typedef struct MazeDirectint Dx; 行標(biāo)int Dy; / 列標(biāo)int direct; /走到下一個(gè)坐標(biāo)點(diǎn)的方向MazeDirect;（2）定義鏈表節(jié)點(diǎn)的結(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）移動(dòng)數(shù)組結(jié)構(gòu)的定義typedef structint x,y;/x 為行標(biāo)，y 為列標(biāo)Directio n_in crem;2:算法的設(shè)計(jì)：【1】迷宮圖的設(shè)計(jì)設(shè)迷宮為 m 行 n 列，利用 mazemn來(lái)表示一個(gè)迷宮，mazeij=0 或 1;其中：0 表示通路，1 表示不通，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有4 個(gè)方向可以試探，（見(jiàn)圖

4、）而四個(gè)角點(diǎn)有2個(gè)方向，其它邊緣點(diǎn)有3 個(gè)方向，為使問(wèn)題簡(jiǎn)單化我們用mazem+2n+2來(lái)表示迷宮，而迷宮的四周的值全部為1。這樣做使問(wèn)題簡(jiǎn)單了，每個(gè)點(diǎn)的試探方向全部為4，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)，同時(shí)與迷宮周?chē)菈Ρ谶@一實(shí)際問(wèn)題相一致。假設(shè)有 6 行 8 列的迷宮，如下圖為maze810構(gòu)造的迷宮【2】試探方向的設(shè)計(jì)：在上述表示迷宮的情況下，每個(gè)點(diǎn)有 4 個(gè)方向去試探，如當(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í)針?lè)较蜻M(jìn)行。為了簡(jiǎn)化問(wèn)題，方便的求

5、出新點(diǎn)的坐標(biāo)，將從正東開(kāi)始沿順時(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;這樣對(duì) move 的設(shè)計(jì)會(huì)很方便地求出從某點(diǎn)（x, y）按某一方向 v （0 v(x , y , d )出棧；求出下一個(gè)要試探的方向 d+ ;/當(dāng)遇到死路的時(shí)候就出棧，尋找原來(lái)點(diǎn)的下一個(gè)方向 while(還有剩余試探方向時(shí)) i

6、f( d 方向可走)則(x , y , d )入棧;求新點(diǎn)坐標(biāo)(i, j );將新點(diǎn)(i , j)切換為當(dāng)前點(diǎn)(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é)點(diǎn)的結(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; 遇到死路的時(shí)候，回溯(通過(guò)出棧完成)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ù)點(diǎn) */ if(x=m&y=n)flag=1;printf(n 到達(dá)迷宮出口：d,%d,x,y);printf(n 經(jīng)過(guò)的節(jié)點(diǎn)有：%d 個(gè),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(”請(qǐng)輸入迷宮圖的行數(shù)和列數(shù)(輸入格式為 i,j)