【正文】 22 頁 共 31 頁 附錄 程序代碼： include include include include include define N 39 define M 39 int X。成員們并沒有因此動怒，而是耐心傾聽和思考，說出每個人的意見，做到了讓每個人都信服。其次，通過團隊合作，我們每個人都感覺到了團隊精神的重要性，它不是說將每個人的想法疊加或簡單拼湊起來，而是需要我們每個人協(xié)調(diào)，汲取每個人的專長和想法的獨到之處，進而整合起來，確定一個完備的方案。而后便是收尾工作，成員們依舊盡心盡力，最終，經(jīng)過我們一周多的努力，我們有了實驗成果。在上機實際操作中，也并不是從一開始就順利的，代碼中出現(xiàn)了不少錯誤，雖然我們一一調(diào)試改正，但在最后還是遇到了瓶頸，大家也都紛紛絞盡腦汁思考問題所在。至于最 后代碼的實現(xiàn)，也是我們小組成員共同努力的結(jié)果。在確定下選題了之后，我們就著手開始準備實現(xiàn)程序的各個步驟。由于數(shù)據(jù)結(jié)構(gòu)這門課本身就比較晦澀和難以理解，我們從剛開始選題就陷入了僵局。 break。\n39。 getchar()。 printf(你的輸入有誤 !\n)。 break。 printf(\t 正在退出系統(tǒng)。 system(cls)。 printf(制作人： \n\n\t\t 劉 暢 \n\n\t\t 周潔 \n\n\t\t 周胡勇 \n\n\n)。//在當前的位置輸出 } 注：其他代碼詳見附錄。//左移 MoveCursorTo(iCol * 2,iRow)。 printf(← )。 迷宮游戲 地圖代碼如下： int iMap[10][20] = {{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,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}}。 } //由于 rand()產(chǎn)生的隨機數(shù)是從 0 到 RAND_MAX //RAND_MAX 是定義在 中的 ,其值至少為 32767) //要產(chǎn)生從 X 到 Y 的數(shù) ,只需要這樣寫： k=rand()%(YX+1)+X。j++) { maze[i][j]=0。i++) for(j=0。 第 16 頁 共 31 頁 for(i=0。jn。im。 system(pause)。 自動生成迷宮代碼如下： void zidong_maze(int m,int n)//自動生成迷宮 { int i,j。 自動生成迷宮有解情況 第 15 頁 共 31 頁 圖 自動生成迷宮界面 用戶自 定義迷宮的行數(shù)和列數(shù)，由系統(tǒng)自動生成迷宮圖 并求出路徑。maze[i][j])。jn。im。 printf(請按行輸入迷宮， 0 表示通路， 1 表示障礙 (用空格隔開 ):\n\n)。 手動輸入迷宮代碼如下： void shoudong_maze(int m,int n)//手動輸入迷宮 { int i,j。 手動生成迷宮有解情況 第 13 頁 共 31 頁 圖 手動生成迷宮界面 用戶自定義迷宮的行數(shù)、列數(shù)、迷宮障礙矩陣，由系統(tǒng)生成對應(yīng)的迷宮并求出路徑。 } 注：具體源代碼 見附錄 第 11 頁 共 31 頁 第 3 章 程序運行結(jié)果與分析 調(diào)試分析 在調(diào)試過程中，首先使用的是棧進行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用 隊列。 case 0: 特別鳴謝 。 case 3: youxi()。 mgpath(maze,m,n)。 case 2 ： 請輸入行列數(shù) (如果超出預(yù)設(shè)范圍則提示重新輸入 ) zidong_maze(m,n)。 mgpath(maze,m,n)。 switch(i) { case 1：請輸入行列數(shù) (如果超出預(yù)設(shè)范圍則提示重新輸入 ) 第 10 頁 共 31 頁 shoudong_maze(m,n)。 搜索算法流程如 圖 所示： 第 9 頁 共 31 頁 圖 迷宮路徑搜索流 程圖 while(cycle!=(1)) ☆ 手動生成迷宮 請按： 1 ☆ 自動生成迷宮 請按： 2 ☆ 進入 迷宮 游戲 請按： 3 ☆ 退出迷宮游戲 請按： 4 ☆ ~~特別鳴謝 ~~ 請按： 0 scanf(%d,amp。 maze[][]==3。 } 訪問到出口 (找到 路徑 )即 ==m1且 ==n1,則逆序?qū)⒙窂綐擞洖?3即 ： maze[][]==3。否則訪問入口節(jié)點，將入口節(jié)點標記為訪問過 maze[][]=2,調(diào)用函數(shù) enqueue(p)將該節(jié)點入隊。調(diào)用enqueue(visit_point),將該節(jié)點入隊 } ⑤路徑求解 void mgpath(int maze[41][41],int m,int n) {先定義入口節(jié)點為 struct point p={0,0,1},從 maze[0][0]開始訪問。為方便操作使其為全局變量 迷宮中節(jié)點類型及隊列類型： struct point{int row,col,predecessor}que[512] (1)手動生成迷宮 void shoudong_maze(int m,int n) {定義 i,j 為循環(huán)變量 for(i=m) for(j=n) 輸入 maze[i][j]的值 } (2)自動生成迷宮 void zidong_maze(int m,int n) {定義 i,j 為循環(huán)變量 for(i=m) for(j=n) maze[i][j]=rand()%2 // 由于 rand() 產(chǎn) 生 的 隨 機 數(shù) 是 從 0 到 RAND_MAX,RAND_MAX 是定義在 中的 ,其值至少為 32767),要產(chǎn)生從 X到Y(jié)的數(shù) ,只需要這樣寫： k=rand()%(YX+1)+X。 表 搜索路徑表 0 1 2 3 4 5 6 7 8 9 10 (0,0) (0,1) (1,1) (1,2) (2,1) (2,2) (1,3) (2,3) (0,3) (3,3) (3,4) 1 0 1 2 2 3 4 5 6 7 9 由此可以看出，得到最短路徑 (3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 輸出的結(jié)果分為兩種，一種是直觀的用圖給出的通路，其中通路用☆表示，第二種輸出的是尋找完后的路徑，路徑用具體的坐標來表示 。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。 注：其中 M， N 分別表示迷宮最大行、列數(shù)，本程序 M、 N 的缺省值為 339，當然，用戶也可根據(jù)需要，調(diào)整其大小。 第 3 頁 共 31 頁 第 2 章 課程設(shè)計總體方案及分析 問題分析 要建立迷宮首先就要建立存儲結(jié)構(gòu)，這里我們用數(shù)組的方式建立的。用戶可以自己定義迷宮并設(shè)置其中的障礙，以矩陣形式輸入，也可通過定義迷宮的行列數(shù)由系統(tǒng)自動生成迷宮。 （ 3）用一種標志（如數(shù)字 8）在迷宮中標出該條通路； 第 2 頁 共 31 頁 （ 4）在屏幕上輸出迷宮和通路； （ 5）上述功能可用菜單選擇。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的矩形迷宮如下圖 A 所示，求出一條從入口到出口的通路，或得出沒有通路的論。對同一只老鼠重復(fù)進行上述實驗，一直到老鼠從入口走到出口，而不 走錯一步。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進方向形成了多處阻擋。 關(guān)鍵詞： 迷宮；窮舉；隊 列。假設(shè)以隊列記錄“當前路徑”，則 隊列中存放的是“當前路徑上最后一個通道塊”