3.3_棧的應(yīng)用--迷宮求解

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

2、 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$迷宮思路 在設(shè)計這個問題時，我考慮到以下幾點：在設(shè)計這個問題時，我考慮到以下幾點： 1、迷宮入口和出口的坐標(biāo)、迷宮入口和出口的坐標(biāo) 2、保存迷宮的、保存迷宮的2維數(shù)組維數(shù)組 3、獲得路徑的函數(shù)、獲得路徑的函數(shù)我們模仿人走迷宮時的思路，設(shè)置一個當(dāng)前點，一個我們模仿人走迷宮時的思路，設(shè)置一個當(dāng)前點，一個目標(biāo)點（下一個要走的點）。初始情況下當(dāng)前點為入

3、目標(biāo)點（下一個要走的點）。初始情況下當(dāng)前點為入口，終止條件為當(dāng)前點為出口，這樣，我們的函數(shù)大口，終止條件為當(dāng)前點為出口，這樣，我們的函數(shù)大概結(jié)構(gòu)就出來了。概結(jié)構(gòu)就出來了。 在從入口到出口的過程中程序?qū)Ξ?dāng)前點的上、下、在從入口到出口的過程中程序?qū)Ξ?dāng)前點的上、下、左、右四個點依次進行判斷，當(dāng)發(fā)現(xiàn)任一個方向是未左、右四個點依次進行判斷，當(dāng)發(fā)現(xiàn)任一個方向是未走過的區(qū)域時，就將當(dāng)前點指向那個點進行嘗試，同走過的區(qū)域時，就將當(dāng)前點指向那個點進行嘗試，同時將當(dāng)前點入棧并做標(biāo)記。而當(dāng)時將當(dāng)前點入棧并做標(biāo)記。而當(dāng)4個方向都不通或已個方向都不通或已走過時，則為死路，標(biāo)記當(dāng)前點為死路并從棧中彈出走過時，則為死路，標(biāo)

4、記當(dāng)前點為死路并從棧中彈出上一個點繼續(xù)進行嘗試，這時因為當(dāng)前點已被標(biāo)記為上一個點繼續(xù)進行嘗試，這時因為當(dāng)前點已被標(biāo)記為死路，則彈出上一個點時就不會重復(fù)這條路，達到尋死路，則彈出上一個點時就不會重復(fù)這條路，達到尋找正確路徑的效果。找正確路徑的效果。描述:n當(dāng)前點:n坐標(biāo)位置(x,y),可用二維數(shù)組實現(xiàn)(seat)n記錄當(dāng)前點探索的方向:din如起點為(1,1),先判斷東(1),南(2),西(3),北(4),順時針方向轉(zhuǎn),判斷其鄰居是否通,不同的話,鄰居轉(zhuǎn)向下一個方向探索,若均不通,則按原路返回,退棧.取棧頂元素,沿下一個方向探索n注意:凡走過的也要標(biāo)記符號:迷宮的分析n迷宮設(shè)置為一個迷宮設(shè)置為一

5、個2維數(shù)組，通路為維數(shù)組，通路為1，不通為，不通為0，但是，但是四周為屏障四周為屏障n設(shè)置一個棧來存儲迷宮的路徑：記錄每個位置的坐標(biāo)設(shè)置一個棧來存儲迷宮的路徑：記錄每個位置的坐標(biāo)值（值（x,y),同時將納入棧中的路徑，記錄它來自何方，同時將納入棧中的路徑，記錄它來自何方，也就是記錄它的探測方向編號（東，南，西，北類似也就是記錄它的探測方向編號（東，南，西，北類似于地圖的指示，于地圖的指示，1，2，3，4）n通的話就入棧操作：（通的話就入棧操作：（x,y,di)n探測當(dāng)前坐標(biāo)位置的所有鄰居均不通：出棧，打上腳探測當(dāng)前坐標(biāo)位置的所有鄰居均不通：出棧，打上腳印，此路不通，不再加入印，此路不通，不再加

6、入n再對棧頂重新探測尋求新的鄰居入棧再對棧頂重新探測尋求新的鄰居入棧n直到達到迷宮出口（有解）或退回到原路的入口（無直到達到迷宮出口（有解）或退回到原路的入口（無解）解）程序流程圖開始迷宮求解構(gòu)建迷宮結(jié)束打印路徑迷宮算法判斷當(dāng)前結(jié)點是否通暢通暢,則記錄該點到棧中,并判斷是為終點,不為終點的話,繼續(xù)前行探索不通暢,則后退,換方向訪問,到?？战Y(jié)束設(shè)置訪問東鄰居開始,若其不通,換方向探路鄰居訪問遍,均不通,退出此結(jié)點,取當(dāng)前棧頂?shù)奈丛L問鄰居探路總結(jié)總結(jié):對于一個入棧的節(jié)點要記錄其位置對于一個入棧的節(jié)點要記錄其位置(x,y),同時同時記錄其探索鄰居的方向記錄其探索鄰居的方向di(1,2,3,4)記錄四

7、個鄰居記錄四個鄰居同時對于已經(jīng)退出的節(jié)點標(biāo)記無需標(biāo)記其同時對于已經(jīng)退出的節(jié)點標(biāo)記無需標(biāo)記其”不不通通”,只要沿下一個方向轉(zhuǎn)圈就可只要沿下一個方向轉(zhuǎn)圈就可.迷宮演示見cd中的遞歸ncd迷宮nDS-Algo-VC下的第三章算法3.3求迷宮路徑算法的基本思想基本思想是：n若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入，則納入路徑，繼續(xù)前進路徑，繼續(xù)前進;n若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后，則后退，換方向繼續(xù)探索退，換方向繼續(xù)探索;n若四周若四周“均無通路均無通路”，則將當(dāng)，則將當(dāng)前位置從路徑中刪除出去。前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通若當(dāng)前位置可通，

8、則則將當(dāng)前位置插入棧頂插入棧頂； 若若該位置是出口位置，則則算法結(jié)束； 否則切換否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； 否則否則 while (棧不空）棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法： 若若棧不空且棧頂位置尚有其他方向未被探索棧不空且棧頂位置尚有其他方向未被探索，則則設(shè)定新的當(dāng)前位置為: 沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊棧頂位置的下一相鄰塊；若若棧不空但棧頂位置的四周均不可通棧不空但棧頂位置的四周均不可通，則則刪去棧頂位置；/ 從路徑中刪去該通道塊 若若棧不空，則則重新測試新的棧頂位置， 直至直至找到一個可通的相鄰塊或出棧

9、至?？眨蝗羧魲？諚？眨瑒t則表明迷宮沒有通路。實驗內(nèi)容 一個mn的迷宮，0：暢通，1：障礙，設(shè)計一個程序，對任意設(shè)定的迷宮，求出從入口到出口的通路。入口：1 1；出口：6 8 0 1 0 1 1 0 1 11 0 0 1 1 0 1 00 1 1 0 0 1 1 11 0 0 1 1 0 0 11 1 0 0 1 1 0 10 1 1 1 0 0 0 0 實現(xiàn)提示1用一種稱為廣度搜索的算法，將迷宮的入 點（1，1）作為第一個出發(fā)點，向四周搜 索可通行的位置，形成第一層新的出發(fā) 點，然后對第一層中各個位置再分別向四 周搜索可通行的位置，形成第二層新的出 發(fā)點，如此進行下去直至到達迷宮的出口 點（m，n）為止。實現(xiàn)提示2為了避免多次檢測是否走到邊沿，將迷宮 周圍各鑲上一條邊，相當(dāng)于在迷宮的周圍 布上一圈不通過的的墻。3為了避免有的點被重復(fù)到達，應(yīng)標(biāo)志已通 過的位置，可以采用一個標(biāo)志數(shù)組來標(biāo)志 已通過了的位置。實現(xiàn)提示4為了記錄搜索過程中到達位置及其出發(fā) 點，可以建立一個結(jié)構(gòu)體數(shù)組，數(shù)組的每 組元素有三個域x，y，pre，其中分別記 錄x和y到達位置的行、列坐標(biāo)，pre記下 其出發(fā)點在數(shù)組中的坐標(biāo)程序流程圖開始迷宮求解構(gòu)建迷宮結(jié)束打印路徑注意問題 1同學(xué)們可以先按照給定的迷宮去做，完 成的情況下可以將迷宮改成可根據(jù)