【正文】 (0,0)4. 輸出結(jié)果輸出的結(jié)果分為兩種，一種是直觀的用圖給出的通路，其中通路用☆表示，第二種輸出的是尋找完后的路徑，路徑用具體的坐標(biāo)來表示。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開始搜索路徑。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為339，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。第2章 課程設(shè)計(jì)總體方案及分析 問題分析要建立迷宮首先就要建立存儲(chǔ)結(jié)構(gòu)，這里我們用數(shù)組的方式建立的。用戶可以自己定義迷宮并設(shè)置其中的障礙，以矩陣形式輸入，也可通過定義迷宮的行列數(shù)由系統(tǒng)自動(dòng)生成迷宮。（3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路；（4）在屏幕上輸出迷宮和通路；（5）上述功能可用菜單選擇。設(shè)計(jì)一個(gè)計(jì)算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的論。對(duì)同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口走到出口，而不走錯(cuò)一步。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對(duì)行進(jìn)方向形成了多處阻擋。關(guān)鍵詞：迷宮；窮舉；隊(duì)列。假設(shè)以隊(duì)列記錄“當(dāng)前路徑”，則隊(duì)列中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。因此，在求迷宮通路的算法中要應(yīng)用“隊(duì)列”的思想假設(shè)“當(dāng)前位置”指的是“在搜索過程中的某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。華 北 科 技 學(xué) 院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書班級(jí) 小組成員:______成績(jī): _____小組成員: 成績(jī): _____小組成員: _成績(jī): _____設(shè)計(jì)題目:_____ 迷宮問題 _______ 設(shè)計(jì)時(shí)間: 至 指導(dǎo)教師:___ _____________ 評(píng) 語(yǔ):________________________________ _________________________________________ _________________________________________ _________________________________________ 評(píng)閱教師: _____________目錄設(shè)計(jì)總說明 II第1章 課程設(shè)計(jì)內(nèi)容和要求 1 1 1 2第2章 課程設(shè)計(jì)總體方案及分析 3 問題分析 3 系統(tǒng)總體設(shè)計(jì) 4 6第3章 程序運(yùn)行結(jié)果與分析 11 調(diào)試分析 11 測(cè)試結(jié)果 11第4章 心得總結(jié) 20參考文獻(xiàn) 21附錄 22設(shè)計(jì)總說明：本課程設(shè)計(jì)是解決迷宮求解的問題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，需要用一個(gè)保存從入口到當(dāng)前位置的路徑的結(jié)構(gòu)。所謂“下一位置”指的是當(dāng)前位置四周4個(gè)方向（上、下、左、右）上相鄰的方塊。由此，“納入路徑”的操作即為“當(dāng)前位置入隊(duì)”；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出隊(duì)”。第1章 課程設(shè)計(jì)內(nèi)容和要求 迷宮問題是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。老鼠經(jīng)過多次試驗(yàn)最終學(xué)會(huì)走通迷宮的路線。 要求設(shè)計(jì)程序輸出如下：(1) 建立一個(gè)大小為mn的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動(dòng)生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點(diǎn) 的坐標(biāo)。用戶進(jìn)入菜單頁(yè)面選擇迷宮的狀態(tài)（1表示手動(dòng)生成迷宮，2表示自動(dòng)生成迷宮，3表示迷宮游戲，4表示退出）運(yùn)用本迷宮系統(tǒng)，用戶可以根據(jù)自己的需求輸入所需的迷宮，其中0表示通路，1表示障礙。本系統(tǒng)自帶一迷宮地圖可供用戶娛樂，用戶的最高成績(jī)可以被保存，下次進(jìn)入游戲系統(tǒng)可以刷新紀(jì)錄。根據(jù)用戶輸入的迷宮的大小（我們?cè)O(shè)置的最大值為40可以根據(jù)要求調(diào)解），迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述；迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來存放元素，即可得到一個(gè)mn的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m1,n1)表示迷宮出口位置。首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。以矩陣 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)均入隊(duì)列，且它們的前節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路。 系統(tǒng)總體設(shè)計(jì) 1. 功能結(jié)構(gòu)圖 (1)構(gòu)建一個(gè)二維數(shù)組maze[M+2][N+2]用于存儲(chǔ)迷宮矩陣 (2)自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組maze[M+2][N+2]賦值 (3)構(gòu)建一個(gè)隊(duì)列用于存儲(chǔ)迷宮路徑 (4)建立迷宮節(jié)點(diǎn)struct point,用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問情況 (5)實(shí)現(xiàn)搜索算法 (6)屏幕上顯示操作菜單 (1)主函數(shù) main() (2)手動(dòng)生成迷宮函數(shù) shoudong_maze() (3)自動(dòng)生成迷宮函數(shù) zidong_maze() (4)將迷宮打印成圖形 print_maze() (5)打印迷宮路徑 (若存在路徑) result_maze() (6)迷宮游戲函數(shù) youxi() (7)入隊(duì) enqueue() (8)出隊(duì) dequeue() (9)判斷隊(duì)列是否為空 is_empty() (10)訪問節(jié)點(diǎn) visit() (11)搜索迷宮路徑 mgpath()實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型及操作的偽代碼算法迷宮矩陣類型：int maze[M+2][N+2]。}(3)打印迷宮圖形void print_maze(int m,int n){用i