3.3-棧的應用-迷宮求解解析

3.3棧的應用--迷宮求解例四、迷宮【問題描述】

以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路?；虻贸鰶]有通路的結(jié)論迷宮用計算機來求解方法其實很簡單,就是走遍所有可能的路徑,直到找到出口為止,當走到錯誤的路線的時候,就退回上一個路口交叉點,選擇其他方向.這種思維其實用堆棧(stack)完全可以解決例四、迷宮求解通常用的是“窮舉求解”的方法

11

112

222

232

133

134

424

125

126

416

315

314

43$$$$$$$$迷宮思路

在設(shè)計這個問題時，我考慮到以下幾點：

1、迷宮入口和出口的坐標

2、保存迷宮的2維數(shù)組

3、獲得路徑的函數(shù)

我們模仿人走迷宮時的思路，設(shè)置一個當前點，一個目標點（下一個要走的點）。初始情況下當前點為入口，終止條件為當前點為出口，這樣，我們的函數(shù)大概結(jié)構(gòu)就出來了。

在從入口到出口的過程中程序?qū)Ξ斍包c的上、下、左、右四個點依次進行判斷，當發(fā)現(xiàn)任一個方向是未走過的區(qū)域時，就將當前點指向那個點進行嘗試，同時將當前點入棧并做標記。而當4個方向都不通或已走過時，則為死路，標記當前點為死路并從棧中彈出上一個點繼續(xù)進行嘗試，這時因為當前點已被標記為死路，則彈出上一個點時就不會重復這條路，達到尋找正確路徑的效果。

描述:當前點:坐標位置(x,y),可用二維數(shù)組實現(xiàn)(seat)記錄當前點探索的方向:di如起點為(1,1),先判斷東(1),南(2),西(3),北(4),順時針方向轉(zhuǎn),判斷其鄰居是否通,不同的話,鄰居轉(zhuǎn)向下一個方向探索,若均不通,則按原路返回,退棧.取棧頂元素,沿下一個方向探索注意:凡走過的也要標記符號:迷宮的分析迷宮設(shè)置為一個2維數(shù)組，通路為1，不通為0，但是四周為屏障設(shè)置一個棧來存儲迷宮的路徑：記錄每個位置的坐標值（x,y),同時將納入棧中的路徑，記錄它來自何方，也就是記錄它的探測方向編號（東，南，西，北類似于地圖的指示，1，2，3，4）通的話就入棧操作：（x,y,di)探測當前坐標位置的所有鄰居均不通：出棧，打上腳印，此路不通，不再加入再對棧頂重新探測尋求新的鄰居入棧直到達到迷宮出口（有解）或退回到原路的入口（無解）程序流程圖開始迷宮求解構(gòu)建迷宮結(jié)束打印路徑迷宮算法判斷當前結(jié)點是否通暢通暢,則記錄該點到棧中,并判斷是為終點,不為終點的話,繼續(xù)前行探索不通暢,則后退,換方向訪問,到?？战Y(jié)束設(shè)置訪問東鄰居開始,若其不通,換方向探路鄰居訪問遍,均不通,退出此結(jié)點,取當前棧頂?shù)奈丛L問鄰居探路總結(jié):對于一個入棧的節(jié)點要記錄其位置(x,y),同時記錄其探索鄰居的方向di(1,2,3,4)記錄四個鄰居同時對于已經(jīng)退出的節(jié)點標記無需標記其”不通”,只要沿下一個方向轉(zhuǎn)圈就可.迷宮演示見cd中的遞歸cd迷宮DS-Algo-VC下的第三章算法3.3求迷宮路徑算法的基本思想是：若當前位置“可通”，則納入路徑，繼續(xù)前進;若當前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當前位置從路徑中刪除出去。設(shè)定當前位置的初值為入口位置；

do｛

若當前位置可通，

則｛將當前位置插入棧頂；

若該位置是出口位置，則算法結(jié)束；否則切換當前位置的東鄰方塊為新的當前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的算法：

……若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當前位置為:沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至棧空；｝若棧空，則表明迷宮沒有通路。實驗內(nèi)容

一個m×n的迷宮，0：暢通，1：障礙，設(shè)計一個程序，對任意設(shè)定的迷宮，求出從入口到出口的通路。入口：11；出口：68

010110111001101001100111100110011100110101110000

實現(xiàn)提示1．用一種稱為廣度搜索的算法，將迷宮的入點（1，1）作為第一個出發(fā)點，向四周搜索可通行的位置，形成第一層新的出發(fā)點，然后對第一層中各個位置再分別向四周搜索可通行的位置，形成第二層新的出發(fā)點，如此進行下去直至到達迷宮的出口點（m，n）為止。實現(xiàn)提示2．為了避免多次檢測是否走到邊沿，將迷宮周圍各鑲上一條邊，相當于在迷宮的周圍布上一圈不通過的的墻。3．為了避免有的點被重復到達，應標志已通過的位置，可以采用一個標志數(shù)組來標志已通過了的位置。實現(xiàn)提示4．為了記錄搜索過程中到達位置及其出發(fā)點，可以建立一個結(jié)構(gòu)體數(shù)組，數(shù)組的每組元素有三個域x，y，pre，其中分別記錄x和y到達位置的行、列坐標，pre記下其出發(fā)點在數(shù)組中的坐標程序流程圖開始迷宮求解構(gòu)建迷宮結(jié)束打印路徑注意問題

1．同學們可以先按照給定的迷宮去做，完成的情況下可以將迷宮改成可根據(jù)輸入變化的任意迷宮。

2．注意數(shù)組表示的迷宮下標和現(xiàn)實迷宮下標的不同。

3．跟蹤迷宮求解過程中程序的執(zhí)行情