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

1、利用棧實現(xiàn)迷宮的求解利用棧實現(xiàn)迷宮的求解一、要解決的四個問題：一、要解決的四個問題：1、表示迷宮的數(shù)據(jù)結(jié)構(gòu)：、表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用maze[m][n]來表示一個迷宮，maze[i][j]=0或1其中：0表示通路，1表示不通，當(dāng)從某點向下試探時，中間點有4個方向可以試探，（見圖）而四個角點有2個方向，其它邊緣點有3個方向，為使問題簡單化我們用maze[m2][n2]來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡

2、單了，每個點的試探方向全部為4，不用再判斷當(dāng)前點的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相一致。如圖3.4表示的迷宮是一個68的迷宮。入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。入口(11)01234567890111111111111011101111210010111113100000001141001101111511000100016101100010171111111111出口(68)圖1用maze[m2][n2]表

3、示的迷宮迷宮的定義如下：#definem6迷宮的實際行#definen8迷宮的實際列intmaze[m2][n2]2、試探方向：、試探方向：在上述表示迷宮的情況下，每個點有4個方向去試探，如當(dāng)前點的坐標(biāo)(xy)，與其相鄰的4個點的坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，如圖2所示。因為出口在（m，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進(jìn)行。為了簡化問題，方便的求出新點的坐標(biāo)，將從正東開始沿順時針進(jìn)行的這4個方

4、向（用0，1，2，3表示東、南、西、北）的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move[4]中，在move數(shù)組mnintxyd橫縱坐標(biāo)及方向datatype棧的定義為：SeqStacks4.如何防止重復(fù)到達(dá)某點，以避免發(fā)生死循環(huán)：如何防止重復(fù)到達(dá)某點，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個標(biāo)志數(shù)組mark[m][n]，它的所有元素都初始化為0，一旦到達(dá)了某一點(ij)之后，使mark[i][j]置1，下次再試探這個位置時就不能再走了。另一種方法是

5、當(dāng)?shù)竭_(dá)某點（ij）后使maze[i][j]置1，以便區(qū)別未到達(dá)過的點，同樣也能起到防止走重復(fù)點的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。二、迷宮求解算法思想如下：二、迷宮求解算法思想如下：(1)棧初始化(2)將入口點坐標(biāo)及到達(dá)該點的方向（設(shè)為1）入棧(3)while(棧不空)棧頂元素＝＞（xyd）出棧求出下一個要試探的方向dwhile（還有剩余試探方向時）if（d方向可走）則（xyd）入棧求新點坐標(biāo)(ij)將新點（ij）切換為當(dāng)

6、前點（xy）if((xｙ)==(ｍn))結(jié)束else重置d=0elsed算法如下：intpath(intdatetypetempintxydijtemp.x=1temp.y=1temp.d=1Push_SeqStack(s，temp)阿while(!Empty_SeqStack(s))Pop_SeqStack(s＆temp)x=temp.xy=temp.yd=temp.d1while(d4)i=xmove[d].xj=ymove[d].