《大數(shù)據(jù)結(jié)構(gòu) 迷宮求解》由會(huì)員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu) 迷宮求解（12頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、【完成題目3】迷宮求解【問題描述】以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?！靖疽蟆渴紫葘?shí)現(xiàn)一個(gè)棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向?！舅惴ㄔO(shè)計(jì)】本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)手動(dòng)或者自動(dòng)生成一個(gè)nm矩陣的迷宮，尋找一條從入口點(diǎn)到出口點(diǎn)的通路。我們將其簡(jiǎn)化成具體實(shí)驗(yàn)內(nèi)容如下：選擇手動(dòng)或者自動(dòng)生成一個(gè)nm的迷宮，將迷宮的左上角作入口，右下角作出口，設(shè)“0為通路，“1為障礙，即無法穿越
2、。假設(shè)從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上、下、左、右、左上、左下、右上、右下8個(gè)方向行走。如果迷宮可以走通，如此用“代表“1，用“代表“0，用“代表行走迷宮的路徑。輸出迷宮原型圖、迷宮路線圖以與迷宮行走路徑。如果迷宮為死迷宮，輸出信息。可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，用戶指定入口下標(biāo)和出口下標(biāo)。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。本程序包含三個(gè)模塊1)主程序模塊：void main() 初始化; do 承受命令; 處理命令; while (命令! = 退出); 2)棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型；3)迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型?！驹创a
3、】#include /庫中包含system(pause)和rand()函數(shù)#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請(qǐng)按行輸入迷宮，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、，請(qǐng)重新輸入; Init_hand_Maze(maze,m,n); void Init_automatic_Maze(int mazeMN,int m,int n) /自動(dòng)生成迷宮int i,j;coutn迷宮生成中nn;system(pause);for(i=1;im+1;i+)for(j=1;jn+1;j+)mazeij=rand()%2; /隨機(jī)生成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;/來這一點(diǎn)時(shí)的方向，0右1下2左3上 MazePath(S,e,maze,m,n); else if(S.top!=S.base&S.over!=1) switch(e.direc) /回到上一位置并同時(shí)改變方向
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 歡迎進(jìn)入迷宮求解系統(tǒng)n; coutendl; cout*n; cout 1 手動(dòng)生成迷宮 n; cout 2 自動(dòng)生成迷宮 n; cout 3 退出 nn; cout*n; coutn; couti; switch(i) case 1: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(
11、1-49,1-49),請(qǐng)重新輸入：nn; coutm; coutn; coutn; Init_hand_Maze(maze,m,n); PrintMaze(maze,m,n); MazeType start,end; cout請(qǐng)輸入起點(diǎn)m n:start.mstart.n; start.direc=0; cout請(qǐng)輸入終點(diǎn)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); /承受一個(gè)輸入，當(dāng)為回車時(shí)執(zhí)行break跳出，否如此一直執(zhí)行承受數(shù)據(jù) break; case 2: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請(qǐng)重新輸入：nn; coutm; coutn; coutn; Init_automatic_Maze(maze,m,n); PrintMaze(maze,m,n); cout請(qǐng)輸入起點(diǎn)m n:start.mstart.n; start.direc=0; co
13、ut請(qǐng)輸入終點(diǎn)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; 【結(jié)果截圖】迷宮無解的情況手動(dòng)生成迷宮的情況自動(dòng)生成迷宮的情況【收獲與體會(huì)】1. 本次實(shí)驗(yàn)核心算法明晰，思路明確，易于實(shí)現(xiàn)。遇到的問題是，迷宮的外圍假如未設(shè)置障礙，用此程序采用的求解迷宮路徑的算法無法獲得正確結(jié)果。2. 本程序的MazePath算法代碼不夠簡(jiǎn)潔，但不影響算法實(shí)現(xiàn)。3. 本次實(shí)驗(yàn)由于時(shí)間問題和知識(shí)水平有限，還存在一些問題，比如：界面比擬單調(diào)，整個(gè)程序的功能還不完善，還有界面做的有些簡(jiǎn)單，菜單沒有做好，可進(jìn)展的操作太少，都有待進(jìn)一步改善。4本次實(shí)驗(yàn)使我對(duì)迷宮游戲的原理有了一定的了解，但做出的結(jié)果離真正的迷宮還有很大差距，還需要進(jìn)一步完善，需要自己課下學(xué)習(xí)更多的知識(shí)。
大數(shù)據(jù)結(jié)構(gòu) 迷宮求解
