數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮問題

1、華 北 科 技 學(xué) 院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書班級 小組成員:_成績: _小組成員: 成績: _小組成員: _成績: _設(shè)計題目:_ 迷宮問題 _ 設(shè)計時間: 2013.7.1 至 2013.7.5 指導(dǎo)教師:_ _ 評 語:_ _ _ _ 評閱教師: _目錄設(shè)計總說明II第1章 課程設(shè)計內(nèi)容和要求11.1問題描述11.2設(shè)計要求11.3需求分析2第2章 課程設(shè)計總體方案及分析32.1 問題分析32.2 系統(tǒng)總體設(shè)計42.3系統(tǒng)詳細(xì)設(shè)計6第3章 程序運(yùn)行結(jié)果與分析113.1 調(diào)試分析113.2 測試結(jié)果11第4章 心得總結(jié)20參考文獻(xiàn)21附錄22設(shè)計總說明：本課程設(shè)計是解決迷宮求解的問題，從入口

2、出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，需要用一個保存從入口到當(dāng)前位置的路徑的結(jié)構(gòu)。因此，在求迷宮通路的算法中要應(yīng)用“隊列”的思想假設(shè)“當(dāng)前位置”指的是“在搜索過程中的某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個方

3、塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是當(dāng)前位置四周4個方向（上、下、左、右）上相鄰的方塊。假設(shè)以隊列記錄“當(dāng)前路徑”，則隊列中存放的是“當(dāng)前路徑上最后一個通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入隊”；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出隊”。關(guān)鍵詞：迷宮；窮舉；隊列。第1章 課程設(shè)計內(nèi)容和要求1.1問題描述 迷宮問題是取自心理學(xué)的一個古典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進(jìn)方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對同一只老鼠重復(fù)進(jìn)行上述實驗，

4、一直到老鼠從入口走到出口，而不走錯一步。老鼠經(jīng)過多次試驗最終學(xué)會走通迷宮的路線。設(shè)計一個計算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的論。                                   

5、                    圖1.1矩形迷宮圖1.2設(shè)計要求要求設(shè)計程序輸出如下：(1) 建立一個大小為m×n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點 的坐標(biāo)。（3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路；（4）在屏幕上輸出迷宮和通路；（5）上述功能可用菜單選擇。1.3需求分析1

6、、用戶進(jìn)入菜單頁面選擇迷宮的狀態(tài)（1表示手動生成迷宮，2表示自動生成迷宮，3表示迷宮游戲，4表示退出）2、運(yùn)用本迷宮系統(tǒng)，用戶可以根據(jù)自己的需求輸入所需的迷宮，其中0表示通路，1表示障礙。用戶可以自己定義迷宮并設(shè)置其中的障礙，以矩陣形式輸入，也可通過定義迷宮的行列數(shù)由系統(tǒng)自動生成迷宮。3、本系統(tǒng)自帶一迷宮地圖可供用戶娛樂，用戶的最高成績可以被保存，下次進(jìn)入游戲系統(tǒng)可以刷新紀(jì)錄。第2章 課程設(shè)計總體方案及分析2.1 問題分析1.迷宮的建立要建立迷宮首先就要建立存儲結(jié)構(gòu)，這里我們用數(shù)組的方式建立的。根據(jù)用戶輸入的迷宮的大?。ㄎ覀冊O(shè)置的最大值為40可以根據(jù)要求調(diào)解），迷宮中存在通路和障礙，為了方便迷

7、宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述；2.迷宮的存儲迷宮是一個矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數(shù)組mazeM+2N+2,然后用它的前m行n列來存放元素，即可得到一個m×n的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。3.迷宮路徑的搜索首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一

8、條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時保留搜索痕跡，在考慮進(jìn)入下一個位置搜索之前，將當(dāng)前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(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)(序號0)放入隊列中

9、，其前節(jié)點為空，從它開始搜索，其標(biāo)記變?yōu)?，由于其只有一個非障礙位置，所以接下來移動到(0,1)(序號1)，其前節(jié)點序號為0，標(biāo)記變?yōu)?，然后從(0,1)移動到(1,1)(序號2)，放入隊列中，其前節(jié)點序號為1，(1,1)存在(1，2)(序號3)、(2，1)(序號4)兩個可移動位置，其前節(jié)點序號均為2.對于每一個非障礙位置，它的相鄰非障礙節(jié)點均入隊列，且它們的前節(jié)點序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點的位置，逆序就可以找到其從出口到入口的通路，搜索路徑如表2.1所示。表2.1 搜索路徑表012345678910(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,

10、3)(2,3)(0,3)(3,3)(3,4)-10122345679由此可以看出，得到最短路徑(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)4. 輸出結(jié)果輸出的結(jié)果分為兩種，一種是直觀的用圖給出的通路，其中通路用表示，第二種輸出的是尋找完后的路徑，路徑用具體的坐標(biāo)來表示。2.2 系統(tǒng)總體設(shè)計 1. 功能結(jié)構(gòu)圖圖2.2功能結(jié)構(gòu)圖2.迷宮系統(tǒng)概要設(shè)計 (1)構(gòu)建一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣 (2)自動或手動生成迷宮，即為二維數(shù)組mazeM+2N+2賦值 (3)構(gòu)建一個隊列用于存儲迷宮路徑 (4)建立迷宮節(jié)點struct point,用于存儲迷宮

11、中每個節(jié)點的訪問情況 (5)實現(xiàn)搜索算法 (6)屏幕上顯示操作菜單3.程序中的函數(shù) (1)主函數(shù) main() (2)手動生成迷宮函數(shù) shoudong_maze() (3)自動生成迷宮函數(shù) zidong_maze() (4)將迷宮打印成圖形 print_maze() (5)打印迷宮路徑 (若存在路徑) result_maze() (6)迷宮游戲函數(shù) youxi() (7)入隊 enqueue() (8)出隊 dequeue() (9)判斷隊列是否為空 is_empty() (10)訪問節(jié)點 visit() (11)搜索迷宮路徑 mgpath()2.3系統(tǒng)詳細(xì)設(shè)計實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類

12、型及操作的偽代碼算法1.節(jié)點類型和指針類型迷宮矩陣類型：int mazeM+2N+2;為方便操作使其為全局變量 迷宮中節(jié)點類型及隊列類型： struct pointint row,col,predecessorque5122.迷宮的操作(1)手動生成迷宮void shoudong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n)輸入mazeij的值 (2)自動生成迷宮void zidong_maze(int m,int n)定義i,j為循環(huán)變量 for(i<=m) for(j<=n)mazeij=rand()%2 /由于rand

13、()產(chǎn)生的隨機(jī)數(shù)是從0到 RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;(3)打印迷宮圖形void print_maze(int m,int n)用i,j循環(huán)變量，將mazeij輸出 、(4)打印迷宮路徑void result_maze(int m,int n)用i,j循環(huán)變量，將mazeij輸出 、(5) 搜索迷宮路徑迷宮中隊列入隊操作void enqueue(struct point p)將p放入隊尾，tail+迷宮中隊列出隊操作struct point dequeue(str

14、uct point p)head+,返回quehead-1判斷隊列是否為空int is_empty()返回head=tail的值，當(dāng)隊列為空時，返回0訪問迷宮矩陣中節(jié)點void visit(int row,int col,int maze4141)建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,head-1,mazerowcol=2,表示該節(jié)點以被訪問過;調(diào)用enqueue(visit_point),將該節(jié)點入隊路徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點為struct point p=0,0,-1,從maze00開始訪

15、問。如果入口處即為障礙，則此迷宮無解，返回0 ，程序結(jié)束。否則訪問入口節(jié)點，將入口節(jié)點標(biāo)記為訪問過mazep.rowp.col=2,調(diào)用函數(shù)enqueue(p)將該節(jié)點入隊。判斷隊列是否為空，當(dāng)隊列不為空時，則運(yùn)行以下操作： 調(diào)用dequeue()函數(shù)，將隊頭元素返回給p，如果p.row=m-1且p.col=n-1,即到達(dá)出口節(jié)點，即找到了路徑，結(jié)束；如果p.col+1<n且mazep.rowp.col+1=0,說明未到迷宮右邊界，且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點入隊標(biāo)記已訪問；如果p.row+1<m且mazep.row+1p.col

16、=0,說明未到迷宮下邊界，且其下方有通路,則visit(p.row+1,p.col,maze),將下方節(jié)點入隊標(biāo)記已訪問；如果p.col-1>0且mazep.rowp.col-1=0,說明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze),將左方節(jié)點入隊標(biāo)記已訪問；如果p.row-1>0且mazep.row-1p.col=0,說明未到迷宮上邊界，且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點入隊標(biāo)記已訪問。訪問到出口(找到路徑)即p.row=m-1且p.col=n-1,則逆序?qū)⒙窂綐?biāo)記為3即：mazep.rowp.

17、col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3;最后將路徑圖形打印出來。搜索算法流程如圖2.3所示：圖2.3 迷宮路徑搜索流程圖 3. 菜單選擇while(cycle!=(-1) 手動生成迷宮 請按：1 自動生成迷宮 請按：2 進(jìn)入迷宮游戲 請按：3 退出迷宮游戲 請按：4 特別鳴謝 請按：0 scanf("%d",&i); switch(i) case 1：請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) shoudong_maze(m,n); print_maze(m,n);

18、 mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 2 ：請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 3: youxi(); case 4：cycle=(-1); case 0: 特別鳴謝;break;注：具體源代碼見附錄第3章 程序運(yùn)行結(jié)果與分析3.1 調(diào)試分析在調(diào)試過程中，首先使用的是棧進(jìn)行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用隊列。3.2 測

19、試結(jié)果1.迷宮系統(tǒng)主界面 圖3.1 迷宮系統(tǒng)主界面2. 手動生成迷宮2.1 手動生成迷宮無解情況圖3.2 手動生成迷宮界面用戶自定義迷宮的行數(shù)、列數(shù)、迷宮障礙矩陣，由系統(tǒng)生成對應(yīng)的迷宮并求出無解。2.2 手動生成迷宮有解情況 圖3.3 手動生成迷宮界面用戶自定義迷宮的行數(shù)、列數(shù)、迷宮障礙矩陣，由系統(tǒng)生成對應(yīng)的迷宮并求出路徑。上面測試?yán)又?，路徑為?,0）(1,0)(1,1)(2,1)(2,2)(3,2)(3,3)，在圖中用“”表示。手動輸入迷宮代碼如下：void shoudong_maze(int m,int n)/手動輸入迷宮int i,j;printf("nn");p

20、rintf("請按行輸入迷宮，0表示通路，1表示障礙(用空格隔開):nn");for(i=0;i<m;i+)for(j=0;j<n;j+) scanf("%d",&mazeij);3. 自動生成迷宮3.1自動生成迷宮無解情況圖3.4 自動生成迷宮界面用戶自定義迷宮的行數(shù)和列數(shù)，由系統(tǒng)自動生成迷宮圖并求出上例迷宮無解。3.2 自動生成迷宮有解情況圖3.5 自動生成迷宮界面用戶自定義迷宮的行數(shù)和列數(shù)，由系統(tǒng)自動生成迷宮圖并求出路徑。上面測試?yán)又?，路徑為?,0）(0,1)(0,2)(0,3)(0,4)(1,4)(2,4)（3,4）（4,

21、4），在圖中用“”表示。自動生成迷宮代碼如下：void zidong_maze(int m,int n)/自動生成迷宮int i,j;printf("n迷宮生成中nn");system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2;for(i=0;i<3;i+)for(j=0;j<3;j+)mazeij=0;mazem-1-in-1-j=0;/由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX/RAND_MAX是定義在stdlib.h中的,其值至少為32767)/要

22、產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X; 4. 迷宮游戲4.1 迷宮游戲主界面圖3.6 迷宮游戲主界面4.2 迷宮游戲過程圖3.7 迷宮游戲過程圖用戶可用上下左右鍵控制迷宮中人物行走方向，控制人物走出迷宮。迷宮游戲地圖代碼如下：int iMap1020 = 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1, 1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1

23、,1,0,1, 1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1, 1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1, 1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1, 1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;其人物行走方向以左為例：if(iMapiRowiCol - 1 = 0)/可以行走M(jìn)oveCu

24、rsorTo(iCol * 2,iRow);printf("");/當(dāng)前位置移動方向 iCol -= 1;/左移MoveCursorTo(iCol * 2,iRow);printf("");/在當(dāng)前的位置輸出注：其他代碼詳見附錄。5.特別鳴謝界面圖3.8 特別鳴謝界面部分代碼如下：system("cls");printf("制作人：nntt劉暢nntt周潔nntt周胡勇nnn");system("pause");system("cls");6.退出迷宮系統(tǒng)第 17 頁 共 3

25、1 頁圖3.9 退出迷宮系統(tǒng)界面部分代碼如下：cycle=(-1);printf("t正在退出系統(tǒng)。nt歡迎下次再來O(_)Onn");break;default:printf("n");printf("你的輸入有誤!n");printf("nPress Enter To Contiue!n");getchar();while(getchar()!='n');break;第4章 心得總結(jié)這是我們小組成員第一次以團(tuán)隊合作的形式參與程序設(shè)計這樣的實驗。由于數(shù)據(jù)結(jié)構(gòu)這門課本身就比較晦澀和難以理解，我們從剛

26、開始選題就陷入了僵局。經(jīng)過我們幾次的討論和商討，最終決定選擇這個符合我們小組成員實際能力的選題迷宮。在確定下選題了之后，我們就著手開始準(zhǔn)備實現(xiàn)程序的各個步驟。我們依據(jù)實驗報告的要求和步驟一項項進(jìn)行規(guī)劃，期間在圖書館查閱了很多資料，小組成員之間也相互學(xué)習(xí)，不懂的地方大家一起討論。至于最后代碼的實現(xiàn)，也是我們小組成員共同努力的結(jié)果。我們不斷改進(jìn)和完善代碼中繁瑣和冗余的部分，力圖寫出一個最簡潔明了又不脫離實際的程序，盡可能做到和現(xiàn)實相貼近。在上機(jī)實際操作中，也并不是從一開始就順利的，代碼中出現(xiàn)了不少錯誤，雖然我們一一調(diào)試改正，但在最后還是遇到了瓶頸，大家也都紛紛絞盡腦汁思考問題所在。當(dāng)然，錯誤最后被

27、我們查找了出來。而后便是收尾工作，成員們依舊盡心盡力，最終，經(jīng)過我們一周多的努力，我們有了實驗成果。 在這次團(tuán)隊合作中，我們都深深體會到學(xué)好專業(yè)知識的重要性，老師上課所教授的基本知識是非常必要的，在真正應(yīng)用到實際選題的時候就凸顯了出來，就以我們小組的選題為例，迷宮問題的基本思想就是棧的問題，如果對棧的知識比較了解，在實現(xiàn)迷宮問題時是不會太吃力的。其次，通過團(tuán)隊合作，我們每個人都感覺到了團(tuán)隊精神的重要性，它不是說將每個人的想法疊加或簡單拼湊起來，而是需要我們每個人協(xié)調(diào)，汲取每個人的專長和想法的獨到之處，進(jìn)而整合起來，確定一個完備的方案。其中非常重要的是，在相互討論和商榷中，爭執(zhí)是不可避免的。成員

28、們并沒有因此動怒，而是耐心傾聽和思考，說出每個人的意見，做到了讓每個人都信服。所以說，通過這次實驗，也使我們小組成員之間的關(guān)系更加和諧和親密。參考文獻(xiàn)1文東,華進(jìn).Visual C+程序設(shè)計基礎(chǔ)與項目實訓(xùn).第1版.北京:中國人民大學(xué)出版社,20092段德亮,余健,張仁才.C#課程設(shè)計案例精編.第1版.北京:清華大學(xué)出版社,20083李翠霞.零基礎(chǔ)學(xué)Visual C+.第2版.北京：機(jī)械工業(yè)出版社，20104李言，李偉明，李賀.Visual C+項目開發(fā)全程實錄.第1版.北京：清華大學(xué)出版社，20085朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)-使用C語言.第四版.北京：電子工業(yè)出版社，20116譚浩強(qiáng).C程序設(shè)計.第三

29、版.北京：清華大學(xué)出版社，2005附錄程序代碼：#include"stdlib.h"#include"stdio.h"#include <windows.h>#include <conio.h>#include <time.h>#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)/手動輸入迷宮in

30、t i,j;printf("nn");printf("請按行輸入迷宮，0表示通路，1表示障礙(用空格隔開):nn");for(i=0;i<m;i+)for(j=0;j<n;j+) scanf("%d",&mazeij);void zidong_maze(int m,int n)/自動生成迷宮int i,j;printf("n迷宮生成中nn");system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2

31、;for(i=0;i<3;i+)for(j=0;j<3;j+)mazeij=0;mazem-1-in-1-j=0;/由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX/RAND_MAX是定義在stdlib.h中的,其值至少為32767)/要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X; void print_maze(int m,int n)/輸出迷宮圖int i,j;printf("n迷宮生成結(jié)果如下:nn");printf("迷宮入口n");printf("");for(i=0;i<m;

32、i+)printf("n");for(j=0;j<n;j+) if(mazeij=0) printf("");/通if(mazeij=1) printf("");/堵printf("迷宮出口n");void result_maze(int m,int n)/輸出探索迷宮結(jié)果int i,j;printf("迷宮通路(用表示)如下所示：nt");for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+)if(mazeij=0|mazei

33、j=2) printf("");/通if(mazeij=1) printf("");/障礙if(mazeij=3) printf("");/路徑void enqueue(struct point p)/增加queuetail=p;tail+;struct point dequeue()/刪除head+;return queuehead-1;int is_empty()/空對return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=

34、row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)/路徑探索X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)printf("n=n");printf("此迷宮無解nn");X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&&(p.col=n-1) break;i

35、f(p.col+1<n)&&(mazep.rowp.col+1=0)visit(p.row,p.col+1,maze);/右 順時針，依次東南西北探索if(p.row+1<m)&&(mazep.row+1p.col=0)visit(p.row+1,p.col,maze);/下if(p.col-1>=0)&&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);/左if(p.row-1>=0)&&(mazep.row-1p.col=0) visit(p.row-1,p.

36、col,maze);/上if(p.row=m-1&&p.col=n-1)/到達(dá)終點printf("n=n");printf("迷宮路徑為：n");printf("(%d,%d)n",p.row,p.col);/輸出當(dāng)前路徑坐標(biāo)mazep.rowp.col=3;/更改通路路徑的值while(p.predecessor!=-1)/前一點為通路p=queuep.predecessor;/循環(huán)尋找前點printf("(%d,%d)n",p.row,p.col);mazep.rowp.col=3;else p

37、rintf("n=n"); printf("此迷宮無解！nn");X=0;return 0;void MoveCursorTo(int iX,int iY)HANDLE hStd = GetStdHandle(STD_OUTPUT_HANDLE);COORD crPlayer = iX,iY;SetConsoleCursorPosition(hStd, crPlayer);void youxi() double t,jl=10;time_t st,en;int iMap1020 = 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

38、1,1, 0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1, 1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1, 1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1, 1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1, 1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1, 1,0,0,0,

39、0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;for(int nI = 0; nI < 10; nI+)for(int nJ = 0; nJ < 20; nJ+)if(iMapnInJ = 1)printf("");elseprintf(" ");printf("n");/打印地圖printf("nnt按Esc退出到主界面。"); printf("n紀(jì)錄%.5fn",jl);int i

40、Row = 1,iCol = 0; /定義人物的坐標(biāo)int iInput = 0;MoveCursorTo(iCol * 2,iRow);time (&st);printf("");/在當(dāng)前的位置輸出bool bRun = true;/表示程序繼續(xù)運(yùn)行while(bRun)iInput = _getch();if(iInput = 27) /用戶按下了ESC鍵system("cls");break;if(iInput = 224)/用戶按下了控制鍵iInput = _getch();switch(iInput)case 75:/左if(iMapi

41、RowiCol - 1 = 0)/可以行走M(jìn)oveCursorTo(iCol * 2,iRow);printf("");/當(dāng)前位置移動方向 iCol -= 1;/左移MoveCursorTo(iCol * 2,iRow);printf("");/在當(dāng)前的位置輸出break;case 72:/上if(iMapiRow - 1iCol = 0)/可以行走 MoveCursorTo(iCol * 2,iRow);printf("");/當(dāng)前位置移動方向iRow -= 1;/上移MoveCursorTo(iCol * 2,iRow);prin

42、tf("");/在當(dāng)前的位置輸出break;case 77:/右if(iCol + 1 >= 20)/到達(dá)終點MoveCursorTo(0,16);printf(" 沖出迷宮！n");time (&en);t=difftime(en,st);printf("游戲用時%.5f sec nn",t);if(t>=jl)printf("o()o 遺憾，再接再厲。nn");else if(t<jl) printf("()/ 好棒，紀(jì)錄刷新！nn");jl=t;bRun = fa

43、lse; /結(jié)束循環(huán)break;if(iMapiRowiCol + 1 = 0)/可以行走M(jìn)oveCursorTo(iCol * 2,iRow);printf(""); /當(dāng)前位置移動方向iCol += 1;/右移MoveCursorTo(iCol * 2,iRow);printf("");/在當(dāng)前的位置輸出break;case 80:/下if(iMapiRow + 1iCol = 0)/可以行走M(jìn)oveCursorTo(iCol * 2,iRow);printf("");/當(dāng)前位置移動方向 iRow += 1;/下移MoveCurs

44、orTo(iCol * 2,iRow); printf("");/在當(dāng)前的位置輸出break;system("cls");void main()double t;time_t start,end;int i,m,n,cycle=0;while(cycle!=(-1)printf("*-*n");printf(" 歡迎進(jìn)入迷宮求解系統(tǒng)nn");printf(" n");printf("*-*n");printf(" 手動生成迷宮 請按：1nn");print

45、f(" 自動生成迷宮 請按：2nn");printf(" 進(jìn)入迷宮游戲 請按：3nn");printf(" 退出迷宮系統(tǒng) 請按：4nn");printf(" 特別鳴謝 請按：0nn");printf("*-*n");printf("n");printf(" 請選擇你的操作：");scanf("%d",&i);switch(i)/手動輸入case 1:system("cls");printf("n請輸入行數(shù)：");scanf("%d",&m);printf("n");printf("請輸入列數(shù)：");scanf("%d",&n);while(m<=0|m>39)|(n<=0|n>39)printf("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請重新輸入：nn&quo