【完成題目3】迷宮求解【問(wèn)題描述】以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論?！靖疽蟆渴紫葘?shí)現(xiàn)一個(gè)棧類型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。【算法設(shè)計(jì)】本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)手動(dòng)或者自動(dòng)生成一個(gè)n×m矩陣的迷宮，尋找一條從入口點(diǎn)到出口點(diǎn)的通路。我們將其簡(jiǎn)化成具體實(shí)驗(yàn)內(nèi)容如下：選擇手動(dòng)或者自動(dòng)生成一個(gè)n×m的迷宮，將迷宮的左上角作入口，右下角作出口，設(shè)“0為通路，“1為障礙，即無(wú)法穿越。假設(shè)從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上、下、左、右、左上、左下、右上、右下8個(gè)方向行走。如果迷宮可以走通，如此用“代表“1，用“代表“0，用“代表行走迷宮的路徑。輸出迷宮原型圖、迷宮路線圖以與迷宮行走路徑。如果迷宮為死迷宮，輸出信息。可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，用戶指定入口下標(biāo)和出口下標(biāo)。為處理方便起見(jiàn)，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。本程序包含三個(gè)模塊1)主程序模塊：void main() 初始化; do 承受命令; 處理命令; while (命令! = 退出); 2)棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型；3)迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型?！驹创a】#include<stdlib.h> /庫(kù)中包含system("pause")和rand()函數(shù)#include<stdio.h> /c語(yǔ)言里的庫(kù)#include<iostream>#include <malloc.h>#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 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;i<m+1;i+) for(j=1;j<n+1;j+) cin>>mazeij; for(i=1;i<m+1;i+) for(j=1;j<n+1;j+) if(mazeij!=0&&mazeij!=1) cout<<" 您輸入有誤，請(qǐng)重新輸入" Init_hand_Maze(maze,m,n); void Init_automatic_Maze(int mazeMN,int m,int n) /自動(dòng)生成迷宮int i,j;cout<<"n迷宮生成中nn"system("pause");for(i=1;i<m+1;i+)for(j=1;j<n+1;j+)mazeij=rand()%2; /隨機(jī)生成0、1void PrintMaze(int mazeMN,int row,int col) int i,j; cout<<"迷宮如下列圖."<<endl; for(i=1;i<row+1;i+) for(j=1;j<col+1;j+) if(mazeij=1) cout<<"" else cout<<"" cout<<endl; Status InitStack(Stack &S) S.base=(LMazeType)malloc(STACK_INIT_SIZE * sizeof(MazeType); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; S.over=0; return OK;Status Push(Stack &S,MazeType e) if(S.top-S.base>=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; return OK;Status MazePath(Stack &S,MazeType &e,int mazeMN,int m,int n) do if(mazee.me.n=0)/0可通，1不可通，2為已走過(guò) 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;/來(lái)這一點(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í)改變方向走下一步 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) cout<<"n=n" cout<<"此迷宮無(wú)解nn" return ERROR; MazeType e; while(S.top!=S.base) Pop(S,e); mazee.me.n=(e.direc+10); cout<<"完成!"<<endl; cout<<"n=n" cout<<"路徑為:"<<endl; int i,j; for(i=1;i<row+1;i+) for(j=1;j<col+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<<"" break; cout<<endl; 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" cout<<endl; cout<<"*n" cout<<" 1 手動(dòng)生成迷宮 n" cout<<" 2 自動(dòng)生成迷宮 n" cout<<" 3 退出 nn" cout<<"*n" cout<<"n" cout<<"請(qǐng)選擇你的操作：n" cin>>i; switch(i) case 1: cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; while(m<1|m>49)|(n<1|n>49) cout<<"n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(1-49,1-49),請(qǐng)重新輸入：nn" cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; Init_hand_Maze(maze,m,n); PrintMaze(maze,m,n); MazeType start,end; cout<<"請(qǐng)輸入起點(diǎn)m n:"<<endl; cin>>start.m>>start.n; start.direc=0; cout<<"請(qǐng)輸入終點(diǎn)m n:"<<endl;cin>>end.m>>end.n; Stack S; cout<<"尋找路徑."<<endl; InitStack(S); MazePath(S,start,maze,end.m,end.n); PrintPath(S,maze,m,n);system("pause"); cout<<"nnPress Enter Contiue!n" getchar(); while(getchar()!='n'); /承受一個(gè)輸入，當(dāng)為回車時(shí)執(zhí)行break跳出，否如此一直執(zhí)行承受數(shù)據(jù) break; case 2: cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; while(m<0|m>49)|(n<0|n>49) cout<<"n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請(qǐng)重新輸入：nn" cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; Init_automatic_Maze(maze,m,n); PrintMaze(maze,m,n); cout<<"請(qǐng)輸入起點(diǎn)m n:"<<endl; cin>>start.m>>start.n; start.direc=0; cout<<"請(qǐng)輸入終點(diǎn)m n:"<<endl; cin>>end.m>>end.n; cout<<"尋找路徑."<<endl; InitStack(S); MazePath(S,start,maze,end.m,end.n); PrintPath(S,maze,m,n); system("pause"); cout<<"nnPress Enter Contiue!n" getchar(); while(getchar()!='n'); break; case 3: cycle=(-1);break; default: cout<<"n"cout<<"你的輸入有誤!n" cout<<"nPress Enter Contiue!n" getchar(); while(getchar()!='n'); break; 【結(jié)果截圖】迷宮無(wú)解的情況手動(dòng)生成迷宮的情況自動(dòng)生成迷宮的情況【收獲與體會(huì)】1. 本次實(shí)驗(yàn)核心算法明晰，思路明確，易于實(shí)現(xiàn)。遇到的問(wèn)題是，迷宮的外圍假如未設(shè)置障礙，用此程序采用的求解迷宮路徑的算法無(wú)法獲得正確結(jié)果。2. 本程序的MazePath算法代碼不夠簡(jiǎn)潔，但不影響算法實(shí)現(xiàn)。3. 本次實(shí)驗(yàn)由于時(shí)間問(wèn)題和知識(shí)水平有限，還存在一些問(wèn)題，比如：界面比擬單調(diào)，整個(gè)程序的功能還不完善，還有界面做的有些簡(jiǎn)單，菜單沒(méi)有做好，可進(jìn)展的操作太少，都有待進(jìn)一步改善。4本次實(shí)驗(yàn)使我對(duì)迷宮游戲的原理有了一定的了解，但做出的結(jié)果離真正的迷宮還有很大差距，還需要進(jìn)一步完善，需要自己課下學(xué)習(xí)更多的知識(shí)。