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

3.3棧的應(yīng)用--迷宮求解例四、迷宮【問題描述】

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

11

112

222

232

133

134

424

125

126

416

315

314

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

在設(shè)計(jì)這個(gè)問題時(shí)，我考慮到以下幾點(diǎn)：

1、迷宮入口和出口的坐標(biāo)

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

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

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

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

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

do｛

若當(dāng)前位置可通，

則｛將當(dāng)前位置插入棧頂；

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

｝

否則{

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

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

若棧不空，則重新測(cè)試新的棧頂位置，

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

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

010110111001101001100111100110011100110101110000

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

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

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

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