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

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

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

11

112

222

232

133

134

424

125

126

416

315

314

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

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

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

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

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

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

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

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

do｛

若當前位置可通，

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

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

｝

否則{

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

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

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

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

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

010110111001101001100111100110011100110101110000

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

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

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

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