090620208[雷青青]迷宮問題

1、 西安建筑科技大學(xué)課程設(shè)計(jì)（論文） 課程設(shè)計(jì)（論文）課程名稱： 數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì) 題 目： 迷宮問題 院 （系）： 信息與控制工程學(xué)院 專業(yè)班級(jí)： 計(jì)算機(jī)902 姓 名： 雷青青 學(xué) 號(hào)： 090620208 指導(dǎo)教師： 李智杰 2011 年 9 月 9 日第 20 頁 共20 頁西安建筑科技大學(xué)課程設(shè)計(jì)（論文）任務(wù)書專業(yè)班級(jí)： 計(jì)算機(jī)0902 學(xué)生姓名： 雷青青 指導(dǎo)教師（簽名）： 一、課程設(shè)計(jì)（論文）題目問題描述：以一個(gè)m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。二、本次課程設(shè)計(jì)（論文）應(yīng)達(dá)到的

2、目的數(shù)據(jù)結(jié)構(gòu)是實(shí)踐性很強(qiáng)的課程。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段。課程設(shè)計(jì)要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。本題目要達(dá)到目的：熟練掌握數(shù)組、鏈表的應(yīng)用。 三、本次課程設(shè)計(jì)（論文）任務(wù)的主要內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)參數(shù)、設(shè)計(jì)要求等） 基本要求（1） 實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。（2）編寫遞歸形式的算法，求得迷

3、宮中所有可能的通路；（3）以方陣形式輸出迷宮及其通路。四、應(yīng)收集的資料及主要參考文獻(xiàn)： 由于本課程沒有安排“課內(nèi)上機(jī)”學(xué)時(shí)，因此，在課程設(shè)計(jì)之前必須自己已經(jīng)上機(jī)練習(xí)了“數(shù)組、線性表”及其有關(guān)的基本操作。 參考文獻(xiàn)：1本年級(jí)用的教材：數(shù)據(jù)結(jié)構(gòu)與算法分析（C+版）（第二版）影印版 2005，7；2C+程序設(shè)計(jì)技能百練，中國鐵道出版社，2004，1 蔣立翔編著；3. 數(shù)據(jù)結(jié)構(gòu)與C+，西安交通大學(xué)出版社，1999，11 周葉著；4C/C+與數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，2002，3，1 王立柱；5數(shù)據(jù)結(jié)構(gòu)使用C+語言描述，東南大學(xué)出版社，2001，1，1 陳慧南；五、審核批準(zhǔn)意見教研室主任（簽字） 設(shè)計(jì)總

4、說明迷宮問題是典型的簡(jiǎn)單小游戲，本系統(tǒng)采用Visual C+6.0為開發(fā)工具，迷宮問題的求解是一個(gè)很好的在?；蛘哧?duì)列等方面的應(yīng)用問題，本次設(shè)計(jì)是以棧去實(shí)現(xiàn)的。問題的求解主要是給定一個(gè)入口坐標(biāo)和出口坐標(biāo)時(shí)求出一條從入口到出口的路徑，如果不存在或存在要做出相應(yīng)的判斷，存在時(shí)打印其路徑，并做動(dòng)態(tài)演示。隨著科學(xué)技術(shù)的不斷提高,計(jì)算機(jī)科學(xué)日漸成熟，其強(qiáng)大的功能已為人們深刻認(rèn)識(shí),它已進(jìn)入人類社會(huì)的各個(gè)領(lǐng)域并發(fā)揮著越來越重要的作用。作為計(jì)算機(jī)應(yīng)用的一部分,使用計(jì)算機(jī)對(duì)小游戲的開發(fā)與求解方法,成為不可缺少的一部分，計(jì)算機(jī)的的各種小游戲，在游戲世界中越來越流行。雖然迷宮游戲簡(jiǎn)單常見。但是他的方法，經(jīng)典并且它是一

5、些網(wǎng)絡(luò)游戲的基礎(chǔ)。只有從小的從基礎(chǔ)的開始一步一步邁向更加復(fù)雜化的程序，我們才能從中不斷學(xué)習(xí)，使我們的編程能力不斷加強(qiáng)。 由于計(jì)算機(jī)解迷宮時(shí)，通常用的是群舉的方法，即從入口出發(fā)，順某一方向搜索。若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)搜索，直至所有可能的通路都搜索完為止。為了保證在任何位置上都能沿原路返回，這就需要一個(gè)后進(jìn)先出的結(jié)構(gòu)來存儲(chǔ)起位置，所以用到了棧的概念。迷宮問題相對(duì)來說就是他的求解問題，其次是他的顯示問題，其中用到的各種算法與文件，所產(chǎn)生不同迷宮。相對(duì)我所做的迷宮程序來說，比較簡(jiǎn)單，但是他清楚，明晰的知名迷宮的各種功。因此，在下面的各章中將以開發(fā)這一套小游戲?yàn)槔?談?wù)?/p>

6、其開發(fā)過程和所涉及到的問題及解決方法。 目錄一 緒論················1二 系統(tǒng)需求分析············1三 概要設(shè)計(jì)··············2四 詳細(xì)設(shè)

7、計(jì)··············5五 總結(jié)················11六 致謝················14七 參考文獻(xiàn)

8、3;·············14八 源程序代碼·············15數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮問題一、 緒論1.1課程設(shè)計(jì)選題的目的數(shù)據(jù)結(jié)構(gòu)是實(shí)踐性很強(qiáng)的課程。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段。課程設(shè)計(jì)要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作

9、者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。1.2課題研究的主要內(nèi)容要求完成構(gòu)造迷宮，輸入入口出口，輸出迷宮路徑。功能要求如下：1構(gòu)建迷宮：可以系統(tǒng)構(gòu)建，也可以用戶自己構(gòu)建，輸入1為不通，輸入0為通路。顯示構(gòu)建好的迷宮。2輸出路徑：輸入入口與出口，利用編好的函數(shù)對(duì)迷宮進(jìn)行試探，有路徑輸出路徑，無路徑提示用戶此迷宮無出口。3最短路徑：輸出走出此迷宮的最短路徑，即不用走回頭路的一條路徑。4要求系統(tǒng)有一定的容錯(cuò)性，給用戶必要的提示。二、 系統(tǒng)需求分析2.1輸入/輸出形式迷宮中建立數(shù)組時(shí)，首先輸入迷宮的行數(shù)和列數(shù)。邊圍規(guī)定為1，在程序中已賦值，內(nèi)圍用0、1輸入，不用其他的數(shù)字，若輸入錯(cuò)誤會(huì)提示重新輸入；然

10、后選擇系統(tǒng)創(chuàng)建的迷宮還是自己創(chuàng)建迷宮，輸入選項(xiàng)1或2（輸入其他選項(xiàng)按2處理）；迷宮創(chuàng)建好后，輸入入口和出口坐標(biāo)（入口必須為通路即0，否則系統(tǒng)會(huì)報(bào)錯(cuò)，重新輸入），找到路徑或無路徑；接下來會(huì)提示尋找其他路徑還是退出此迷宮，輸入1或2進(jìn)行選擇；選擇1，則繼續(xù)輸入迷宮入口和出口，選擇2或其他，則退出。若還想創(chuàng)建別的迷宮就在接下來輸入y或Y，輸入其他則退出程序。2.2程序功能在迷宮問題中，可由操作者自己設(shè)定迷宮大小，迷宮內(nèi)部構(gòu)造有兩個(gè)選擇，系統(tǒng)設(shè)計(jì)，節(jié)省時(shí)間，也可由操作者自己設(shè)計(jì)，迷宮入口和出口并能保證入口為通路，若有路徑會(huì)顯示其路徑并顯示最短路徑。一個(gè)迷宮有不同入口和出口，可尋求多條路徑。三、 概要設(shè)

11、計(jì)3.1設(shè)計(jì)思想迷宮中用回溯法從八個(gè)方向向前試探，用隊(duì)列保存探測(cè)到的通路，建立一個(gè)數(shù)組模擬迷宮，將各個(gè)函數(shù)結(jié)合在一起。 走迷宮游戲 主程序退出系統(tǒng)選擇用戶自定義迷宮輸出最短路徑恢復(fù)迷宮輸出整個(gè)路徑判斷每一步所走路徑輸出迷宮圖31 迷宮系統(tǒng)結(jié)構(gòu)圖3.2實(shí)現(xiàn)方法迷宮中定義move數(shù)組，從東順時(shí)針探測(cè)；進(jìn)隊(duì)出隊(duì)完成探測(cè)；自己創(chuàng)建maze數(shù)組，并輸入入口點(diǎn)和出口點(diǎn)，再進(jìn)行計(jì)算。3.3函數(shù)間的關(guān)系創(chuàng)建迷宮輸入進(jìn)口和出口輸出最短路徑輸出路徑開始恢復(fù)迷宮判斷退出此迷宮判斷結(jié)束圖32 函數(shù)流程圖四、 詳細(xì)設(shè)計(jì)4.1實(shí)現(xiàn)定義的數(shù)據(jù)類型（1）迷宮數(shù)組定義為結(jié)構(gòu)體包含兩個(gè)整型數(shù)據(jù)，迷宮出口和入口的值定義為整型。ty

12、pedef structint x,y;item;typedef structint x,y,d;（2）迷宮內(nèi)部的設(shè)計(jì)時(shí)各坐標(biāo)點(diǎn)設(shè)置成棧內(nèi)整型。typedef stack<Datetype> stack_int;（3）迷宮中求路徑和最短路徑時(shí)定義結(jié)構(gòu)體類型表示隊(duì)列，包含整型坐標(biāo)點(diǎn)，和整型下標(biāo)；又有整型的隊(duì)首尾指針。typedef structint x,y;int pre; SqType; ；int front,rear;（4）迷宮路徑和最短路徑輸出時(shí)，遵循棧的規(guī)則，即先進(jìn)后出。int path1(int *maze,int m,int n,int c,int d,int x1,i

13、nt y1)4.2實(shí)現(xiàn)定義操作偽代碼算法迷宮的操作1.手動(dòng)生成迷宮cout<<"請(qǐng)輸入迷宮："<<m<<"行"<<n<<"列"<<", 輸入必須為'0' 或 '1'；"<<endl;for(i=1;i<=m;i+) /輸入第i行迷宮的構(gòu)造；for(j=1;j<=n;j+) /輸入第j列迷宮的結(jié)構(gòu)；cin>>mazeij;A:if(mazeij!=0 && maz

14、eij!=1)cout<<"請(qǐng)?jiān)俅屋斎耄?quot;cin>>mazeij;goto A; /判錯(cuò)；cout<<"迷宮如下："<<endl; /顯示用戶輸入的迷宮；for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)H:cout<<"請(qǐng)輸入迷宮入口(a,b),出口(c,d)："cin>>i>>j>>c>>d;void shoudong_maze(int m,int n)定義i,j為循環(huán)變量for(i<

15、=m)for(j<=n)輸入mazeij的值2.自動(dòng)生成迷宮if(s="1")srand(time(0); /系統(tǒng)時(shí)間隨機(jī)函數(shù)；for(i=1;i<=m;i+)for(j=1;j<=n;j+)mazeij=rand()%2; /隨機(jī)賦值maze11=0; /(1,1)點(diǎn)為可通過點(diǎn)；mazemn=0; /(m,n)點(diǎn)為可通過點(diǎn)；3.打印迷宮路徑void printpath(SqType sq,int)/打印路徑int i;i=rear; docout<<"("<<sqi.x<<","

16、<<sqi.y<<")<-"i=sqi.pre; /回溯；while(i!=-1);4.迷宮恢復(fù)void restore(int *maze,int m,int n)/恢復(fù)迷宮for(int i=1;i<=m;i+)for(int j=1;j<=n;j+)if(mazeij=-1)mazeij=0;5.求一般路徑偽代碼：while(棧不空)棧頂元素=>(x,y,d)出棧;求出下一個(gè)要試探的方向d+;while(還有剩余試探方向)if(d方向可走)(x,y,d)入棧;求新點(diǎn)坐標(biāo)(i,j);將新點(diǎn)(i,j)切換成當(dāng)前點(diǎn)(x,y);

17、if(x,y)=(m,n)結(jié)束;else重置 d=0;else d+;6.求解最短路徑偽代碼：(x,y)入隊(duì);while(隊(duì)列不為空)隊(duì)首元素出隊(duì);for(方向?yàn)?;方向<總方向數(shù);改變方向)到達(dá)點(diǎn)坐標(biāo);if(此坐標(biāo)點(diǎn)為通路)入隊(duì);if(到達(dá)出口點(diǎn))輸出路徑;恢復(fù)迷宮;當(dāng)前點(diǎn)搜索完，取下一點(diǎn)搜索;4.3調(diào)試分析在調(diào)試過程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多條中的一條或不是最短路徑，所以通過算法比較，改用此算法。4.4測(cè)試結(jié)果4.4.1測(cè)試數(shù)據(jù)和結(jié)果1.采用隨機(jī)創(chuàng)建好的迷宮但沒有出路圖41 隨機(jī)輸出結(jié)果圖2，采用自己輸入的迷宮。圖42自己創(chuàng)建迷宮輸出圖43 路徑輸出圖圖44 轉(zhuǎn)換

18、出口輸出路徑圖4.4.2算法時(shí)間復(fù)雜度：O(m²）五、 總 結(jié)5.1問題描述主要問題有：方向設(shè)置，路徑存儲(chǔ)，迷宮圖的存儲(chǔ)，路徑的求解，出口入口的設(shè)置。這個(gè)迷宮問題的算法中，要在開始設(shè)置迷宮的大小。在探索迷宮路線的過程中，是通過不斷的嘗試來得到最終的結(jié)果，由于不能對(duì)已經(jīng)設(shè)定為可走路徑進(jìn)行返回，所以在這個(gè)算法中有時(shí)候可能不能得到走出迷宮的路徑。5.2問題分析1.迷宮的建立：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述，并且先開始建立好迷宮周圍的墻，用1表示。2.迷宮的存儲(chǔ)：迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，然后用它的

19、前m行n列來存放元素，即可得到一個(gè)m×n或m×m的二維數(shù)組，但是他的一個(gè)點(diǎn)是由三個(gè)元素組成，除了行和列，還有一個(gè)指針，即前驅(qū)點(diǎn)的下標(biāo)（），這樣（x,y）,(b,d)表示迷宮的入口與出口。3.迷宮路徑的搜索：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右以及對(duì)角線四個(gè)方向位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)

20、隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。以矩陣 0 0 1 0 1 為例，來示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，將位置(0,0)(序號(hào)0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開始搜索，其標(biāo)記變?yōu)?，由于其只有一個(gè)非障礙位置，所以接下來移動(dòng)到(0,1)(序號(hào)1)，其前節(jié)點(diǎn)序號(hào)為0，標(biāo)記變?yōu)?，然后從(0,1)移動(dòng)到(1,1)(序號(hào)2)，放入隊(duì)列中，其前節(jié)點(diǎn)序號(hào)為1，(1,1)存在(1，2)(序號(hào)3)、(2，1)(序號(hào)4)兩個(gè)可移動(dòng)位置，其前節(jié)點(diǎn)序

21、號(hào)均為2.對(duì)于每一個(gè)非障礙位置，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)列，且它們的前節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路。5.3問題的解決方案迷宮問題中，采用move數(shù)組存儲(chǔ)方向，采用二維數(shù)組存儲(chǔ)迷宮圖，采用棧存儲(chǔ)路徑，采用隊(duì)列算出最短路徑，參數(shù)傳遞出口入口和迷宮的大小。5.4設(shè)計(jì)體會(huì)5.4.1系統(tǒng)的優(yōu)點(diǎn)迷宮問題中，突出優(yōu)點(diǎn)為采用了時(shí)間隨機(jī)函數(shù)，系統(tǒng)自動(dòng)生成迷宮，節(jié)約用戶時(shí)間。此外，用兩種不同的存儲(chǔ)方式（棧和隊(duì)列）對(duì)迷宮進(jìn)行探究。界面清晰、通俗易懂、操作簡(jiǎn)便、結(jié)構(gòu)嚴(yán)謹(jǐn)、邏輯習(xí)慣強(qiáng)。 5.4.2本系統(tǒng)的不足1.對(duì)于迷宮問題，輸入迷宮內(nèi)部結(jié)構(gòu)時(shí)，輸

22、入形式為0、1空格或回車，輸入形式有誤時(shí)，會(huì)使程序無法運(yùn)行下去，有時(shí)還會(huì)進(jìn)入死循環(huán)。輸入入口坐標(biāo)時(shí)，沒有容錯(cuò)，若大于迷宮規(guī)模，程序會(huì)出錯(cuò)。2.迷宮的圖形的構(gòu)建太簡(jiǎn)單，沒有達(dá)到美化效果。而且還有許多自己想到的功能并沒有實(shí)現(xiàn)，有點(diǎn)遺憾。5.4.3可改進(jìn)的地方（1）各個(gè)菜單界面可以設(shè)計(jì)的更為美觀，更簡(jiǎn)潔易懂。（2）可以從各個(gè)方面考慮設(shè)置容錯(cuò)機(jī)制使程序更健壯。（3）可以想辦法把所有的路徑都輸出來，在進(jìn)行排序。（4）迷宮整個(gè)的設(shè)計(jì)太單調(diào)。5.5結(jié)束語課程設(shè)計(jì)中感受到自己知識(shí)的匱乏，需要學(xué)習(xí)的東西很多，不能總是局限于書本，在課程設(shè)計(jì)中出現(xiàn)問題時(shí)，應(yīng)該及時(shí)與周圍同學(xué)交流，多交流才能使學(xué)到的東西更深入到心里，

23、總之，這是一次不錯(cuò)的鍛煉，專業(yè)水平不說能提高什么，但在過程中學(xué)到的學(xué)習(xí)方法應(yīng)該是能受益終生的！六、 致 謝在課程設(shè)計(jì)過程中，由于自己專業(yè)基礎(chǔ)知識(shí)的不扎實(shí)，課程設(shè)計(jì)的時(shí)間總是感覺不夠，在課程設(shè)計(jì)中也遇到了很多困難，好多時(shí)候都想止步不前，但是因?yàn)槲覍懙氖敲詫m，網(wǎng)上資源特別豐富，所以有選擇性的在網(wǎng)上搜尋了許多相關(guān)性的知識(shí)與程序代碼。從而學(xué)習(xí)到了一些有用的知識(shí)。知道了網(wǎng)絡(luò)資源的豐富。同時(shí)因有身邊的舍友與同學(xué)，給與我提意見，鼓勵(lì)我，引導(dǎo)我，以及書本資料的查詢，學(xué)會(huì)了怎么去思考，怎么去解決遇到的問題，怎么讓程序運(yùn)行起來，課程設(shè)計(jì)結(jié)束了，但感覺收獲了很多，不僅僅是任務(wù)完成了，更讓我了解到身邊這群值得我珍惜的

24、朋友是多么的難得以及個(gè)人的知識(shí)能力是多么重要。這僅僅是一個(gè)小小的課程設(shè)計(jì)，以后還要面對(duì)各種各樣的更大的困難與逆境，只要堅(jiān)持，找到正確的方法，相信一切都會(huì)克服的。七、 參考文獻(xiàn)1.Robert L.Kruse , Alexander J.Ryba數(shù)據(jù)結(jié)構(gòu)與算法分析（C+版）（第二版）影印版M.高等教育出版社，2005.72. Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析C+描述M.人民郵電出版社, 2006.11 3. 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版M.清華大學(xué)出版社,2007.034. 周靄如,林偉健.C+程序設(shè)計(jì)基礎(chǔ)（第三版）.電子工業(yè)出版社，2010.01 5. 朱明方,吳及.數(shù)

25、據(jù)結(jié)構(gòu)教程M.機(jī)械工業(yè)出版社,2007.01 /*我真誠地保證： 我自己獨(dú)立地完成了整個(gè)程序從分析、設(shè)計(jì)到編碼的全過程。 如果在上述過程中，我遇到了困難而求教于人，那么，我將在程序報(bào)告中詳細(xì)地列舉我所遇到的問題，以及別人給我的提示。在此，我感謝老師同學(xué)對(duì)我的啟發(fā)和幫助。下面的報(bào)告中，我還會(huì)具體地提到他們?cè)诟鱾€(gè)方法對(duì)我的幫助。 我的程序里中凡是引用到其他程序或文檔之處，例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段,我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。我從未抄襲過別人的程序，也沒有盜用別人的程序，無論是修改式地抄襲還是原封不動(dòng)地抄襲。我編寫這個(gè)程序，從來沒有想過要去破壞或妨

26、礙其他計(jì)算機(jī)系統(tǒng)的正常運(yùn)轉(zhuǎn)。 <雷青青 > */ 八、 源程序代碼#include<iostream>#include<stack>#include<stdio.h>#include<time.h>#include<string>using namespace std;typedef structint x,y;item;typedef structint x,y,d;Datetype;typedef stack<Datetype> stack_int;void path (int *maze,int,int,

27、int,int);void printpath();#define NUM 100 /隊(duì)列大小；typedef structint x,y; /所到點(diǎn)的坐標(biāo)；int pre; /前驅(qū)點(diǎn)的下標(biāo)；SqType; /隊(duì)列；int front,rear; /隊(duì)首指針與隊(duì)尾指針；void printpath(SqType sq,int) /打印路徑;int i;i=rear; docout<<"("<<sqi.x<<","<<sqi.y<<")<-"i=sqi.pre; /回溯；

28、while(i!=-1);void restore(int *maze,int m,int n) /恢復(fù)迷宮for(int i=1;i<=m;i+)for(int j=1;j<=n;j+)if(mazeij=-1)mazeij=0;int path1(int *maze,int m,int n,int c,int d,int x1,int y1) /最短路徑 /m,n為迷宮的長和寬，c，d為迷宮入口坐標(biāo)，x1，y1為迷宮出口坐標(biāo)；maze為迷宮；item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1; /坐標(biāo)增量數(shù)組；SqType sqNU

29、M;int x,y,i,j,v; front=rear=0;sq0.x=c;sq0.y=d;sq0.pre=-1; if(mazecd=0) mazecd=-1; /入口點(diǎn)入隊(duì)；else goto G;while(front<=rear) /隊(duì)列不為空x=sqfront.x;y=sqfront.y;for(v=0;v<8;v+)i=x+movev.x;j=y+movev.y;if(mazeij=0)rear+;sqrear.x=i;sqrear.y=j;sqrear.pre=front;mazeij=-1; /訪問過的坐標(biāo)點(diǎn)，入隊(duì)；if(i=x1&&j=y1)cou

30、t<<"最短路徑為："<<endl;printpath(sq,rear); /輸出路徑；restore(maze,m,n); /恢復(fù)迷宮；return 1; /for v;front+; /當(dāng)前點(diǎn)搜索完，取下一個(gè)點(diǎn)搜索 /whileG:cout<<"無路徑。"<<endl;return 0;void path(int *maze,int a,int b,int m,int n)item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;stack_int st;Date

31、type temp;int x,y,d,i,j;if(mazeab=1)cout<<"進(jìn)口輸入有誤。"return;temp.x=a;temp.y=b;temp.d=-1; /初始化入口點(diǎn)坐標(biāo)及方向；st.push(temp);while(!st.empty()temp=st.top();st.pop();x=temp.x;y=temp.y;d=temp.d+1;while(d<8)i=x+moved.x;j=y+moved.y;if(mazeij=0) /該點(diǎn)可到達(dá)；temp.x=x;temp.y=y;temp.d=d; /坐標(biāo)及方向；st.push(t

32、emp); /坐標(biāo)及方向入棧； x=i;y=j;mazexy=-1; /到達(dá)新點(diǎn)；if(x=m && y=n)cout<<" 迷宮路徑為:"<<endl;cout<<"("<<m<<","<<n<<")<-"Datetype t;while(!st.empty()t=st.top();cout<<"("<<t.x<<","<<

33、;t.y<<")<-"st.pop(); /輸出路徑；cout<<endl;return ; /到達(dá)出口；else d=0; /重新初始化方向；else d+; /改變方向；cout<<"對(duì)不起，無法找到出口."return; /迷宮無路；void printpath()int m,n,i,j,l,c,d;string s;cout<<" 請(qǐng)輸入迷宮的行數(shù)列數(shù)如:(m n)"<<endl;cin>>m>>n;int *maze=new int*m

34、+2;for(i=0;i<=m+1;i+)mazei=new intn+2; /申請(qǐng)迷宮的空間；for(i=0;i<=m+1;i+) mazei0=1;for(i=0;i<=n+1;i+)maze0i=1;for(i=0;i<=m+1;i+)mazein+1=1;for(i=0;i<=n+1;i+)mazem+1i=1; /建立迷宮周圍的墻；cout<<"1、采用創(chuàng)建好的迷宮; 2、自己創(chuàng)建迷宮（其他輸入按'2'處理）"<<endl;cin>>s;if(s="1")srand(time(0); /系統(tǒng)時(shí)間隨機(jī)函數(shù)；for(i=1;i<=m;i+)for(j=1;j<=n;j+)mazeij=rand()%2; /隨機(jī)賦值maze11=0;