【正文】 。因此，在求迷宮通路的算法中要應(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) 語 :________________________________ _________________________________________ _________________________________________ _________________________________________ 評(píng)閱教師 : _____________ I 目錄 設(shè)計(jì)總 說明 .................................................................................................................... II 第 1 章 課程設(shè)計(jì)內(nèi)容和要求 .................................................................................... 1 問題描述 ........................................................................................................... 1 設(shè)計(jì)要求 ........................................................................................................... 1 需求分析 ........................................................................................................... 2 第 2 章 課程設(shè)計(jì)總體方案及分析 ............................................................................ 3 問題分析 .......................................................................................................... 3 系統(tǒng)總體設(shè)計(jì) .................................................................................................. 4 系統(tǒng)詳細(xì)設(shè)計(jì) ................................................................................................... 6 第 3 章 程序運(yùn)行結(jié)果 與 分析 .................................................................................. 11 調(diào)試分析 ........................................................................................................ 11 測(cè)試結(jié)果 ........................................................................................................ 11 第 4 章 心得總結(jié) ...................................................................................................... 20 參考文獻(xiàn) ...................................................................................................................... 21 附錄 .............................................................................................................................. 22 II 設(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 頁 共 31 頁 第 1 章 課程設(shè)計(jì)內(nèi)容和要求 問題描述 迷宮問題是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。老鼠經(jīng)過多次試驗(yàn)最終學(xué)會(huì)走通迷宮的路線。 圖 矩形迷宮圖 設(shè)計(jì)要求 要求設(shè)計(jì)程序輸出如下： (1) 建立一個(gè)大小為 mn 的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動(dòng)生成），并在屏幕上顯示出來； （ 2）找出一條通路的二元組（ i,j）數(shù)據(jù)序列，（ i,j）表示通路上某一 點(diǎn) 的坐標(biāo)。 需求分析 用戶進(jìn)入菜單頁面選擇迷宮的狀態(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è) m n的二維數(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 第 4 頁 共 31 頁 1 0 0 0 1 0 0 1 0 0 首先，將位置 (0,0)(序號(hào) 0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開始搜索，其標(biāo)記變?yōu)?2，由于其只有一個(gè)非障礙位置，所以接下來移動(dòng)到 (0,1)(序號(hào) 1)，其前節(jié)點(diǎn)序號(hào)為 0，標(biāo)記變?yōu)?2，然后從 (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)序號(hào)均為 ，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)列，且它們的前節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路 ，搜 索路徑如表 所示 。 系統(tǒng)總體設(shè)計(jì) 第 5 頁 共 31 頁 進(jìn)入主界面手動(dòng)生成迷宮自