《大數據結構 迷宮求解》由會員分享，可在線閱讀，更多相關《大數據結構 迷宮求解（12頁珍藏版）》請在裝配圖網上搜索。

1、【完成題目3】迷宮求解【問題描述】以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論?！靖疽蟆渴紫葘崿F一個棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個坐標，d表示走到下一坐標的方向。【算法設計】本實驗的目的是設計一個程序，實現手動或者自動生成一個nm矩陣的迷宮，尋找一條從入口點到出口點的通路。我們將其簡化成具體實驗內容如下：選擇手動或者自動生成一個nm的迷宮，將迷宮的左上角作入口，右下角作出口，設“0為通路，“1為障礙，即無法穿越

2、。假設從起點出發(fā)，目的為右下角終點，可向“上、下、左、右、左上、左下、右上、右下8個方向行走。如果迷宮可以走通，如此用“代表“1，用“代表“0，用“代表行走迷宮的路徑。輸出迷宮原型圖、迷宮路線圖以與迷宮行走路徑。如果迷宮為死迷宮，輸出信息?？梢远S數組存儲迷宮數據，用戶指定入口下標和出口下標。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。本程序包含三個模塊1)主程序模塊：void main() 初始化; do 承受命令; 處理命令; while (命令! = 退出); 2)棧模塊實現棧抽象數據類型；3)迷宮模塊實現迷宮抽象數據類型?！驹创a

3、】#include /庫中包含system(pause)和rand()函數#include /c語言里的庫#include#include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define M 49#define N 49using namespace std;int mazeMN; typedef int Status;typedef struct int m,n,direc;MazeType,*LMazeType;typedef

4、struct LMazeType top; LMazeType base; int stacksize; int over;Stack; void Init_hand_Maze(int mazeMN,int m,int n) int i,j; for(i=1;i=m+1;i+) for(j=1;j=n+1;j+) mazeij=1; cout請按行輸入迷宮，0表示通路，1表示障礙:endl; for(i=1;im+1;i+) for(j=1;jmazeij; for(i=1;im+1;i+) for(j=1;jn+1;j+) if(mazeij!=0&mazeij!=1) cout 您輸入有誤

5、，請重新輸入; Init_hand_Maze(maze,m,n); void Init_automatic_Maze(int mazeMN,int m,int n) /自動生成迷宮int i,j;coutn迷宮生成中nn;system(pause);for(i=1;im+1;i+)for(j=1;jn+1;j+)mazeij=rand()%2; /隨機生成0、1void PrintMaze(int mazeMN,int row,int col) int i,j; cout迷宮如下列圖.endl; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) if(mazeij=1

6、) cout; else cout; cout=S.stacksize) S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(MazeType); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(Stack &S,MazeType &e) if(S.top=S.base)return ERROR; e=*-S.top; retu

7、rn OK;Status MazePath(Stack &S,MazeType &e,int mazeMN,int m,int n) do if(mazee.me.n=0)/0可通，1不可通，2為已走過 Push(S,e); mazee.me.n=2; if(e.m=m&e.n=n) S.over=1;/表示存滿一條路徑 return OK; else e.n+; e.direc=0;/來這一點時的方向，0右1下2左3上 MazePath(S,e,maze,m,n); else if(S.top!=S.base&S.over!=1) switch(e.direc) /回到上一位置并同時改變方向

8、走下一步 case 0: e.n-; e.m+; e.direc=1; break; case 1: e.m-; e.n-; e.direc=2; break; case 2: e.n+; e.m-; e.direc=3; break; case 3: Pop(S,e); break; while(S.top!=S.base&S.over!=1); return OK; int PrintPath(Stack S,int mazeMN,int row,int col) if(S.top=S.base) coutn=n; cout此迷宮無解nn; return ERROR; MazeType e

9、; while(S.top!=S.base) Pop(S,e); mazee.me.n=(e.direc+10); cout完成!endl; coutn=n; cout路徑為:endl; int i,j; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) switch(mazeij) case 0: cout; break; case 1: cout; break; case 2: cout; break; case 10: cout; break; case 11: cout; break; case 12: cout; break; case 13: cout;

10、break; coutendl; cout入口endl; cout完成!endl; return OK; int main() int i,m,n,mazeMN,cycle=0; while(cycle!=(-1) cout*n; cout 歡迎進入迷宮求解系統(tǒng)n; coutendl; cout*n; cout 1 手動生成迷宮 n; cout 2 自動生成迷宮 n; cout 3 退出 nn; cout*n; coutn; couti; switch(i) case 1: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數超出預設X圍(

11、1-49,1-49),請重新輸入：nn; coutm; coutn; coutn; Init_hand_Maze(maze,m,n); PrintMaze(maze,m,n); MazeType start,end; cout請輸入起點m n:start.mstart.n; start.direc=0; cout請輸入終點m n:end.mend.n; Stack S; cout尋找路徑.endl; InitStack(S); MazePath(S,start,maze,end.m,end.n); PrintPath(S,maze,m,n);system(pause); coutnnPress

12、 Enter Contiue!n; getchar(); while(getchar()!=n); /承受一個輸入，當為回車時執(zhí)行break跳出，否如此一直執(zhí)行承受數據 break; case 2: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數超出預設X圍(0-49,0-49),請重新輸入：nn; coutm; coutn; coutn; Init_automatic_Maze(maze,m,n); PrintMaze(maze,m,n); cout請輸入起點m n:start.mstart.n; start.direc=0; co

13、ut請輸入終點m n:end.mend.n; cout尋找路徑.endl; InitStack(S); MazePath(S,start,maze,end.m,end.n); PrintPath(S,maze,m,n); system(pause); coutnnPress Enter Contiue!n; getchar(); while(getchar()!=n); break; case 3: cycle=(-1);break; default: coutn;cout你的輸入有誤!n; coutnPress Enter Contiue!n; getchar(); while(getcha

14、r()!=n); break; 【結果截圖】迷宮無解的情況手動生成迷宮的情況自動生成迷宮的情況【收獲與體會】1. 本次實驗核心算法明晰，思路明確，易于實現。遇到的問題是，迷宮的外圍假如未設置障礙，用此程序采用的求解迷宮路徑的算法無法獲得正確結果。2. 本程序的MazePath算法代碼不夠簡潔，但不影響算法實現。3. 本次實驗由于時間問題和知識水平有限，還存在一些問題，比如：界面比擬單調，整個程序的功能還不完善，還有界面做的有些簡單，菜單沒有做好，可進展的操作太少，都有待進一步改善。4本次實驗使我對迷宮游戲的原理有了一定的了解，但做出的結果離真正的迷宮還有很大差距，還需要進一步完善，需要自己課下學習更多的知識。