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

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

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

3、示的迷宮迷宮的定義如下：#definem6迷宮的實(shí)際行#definen8迷宮的實(shí)際列intmaze[m2][n2]2、試探方向：、試探方向：在上述表示迷宮的情況下，每個(gè)點(diǎn)有4個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(xy)，與其相鄰的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è)方

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

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

6、前點(diǎn)（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].