完整版數(shù)據(jù)結(jié)構(gòu)迷宮求解

1、【完成題目3迷宮求解【問(wèn)題描述】以一個(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)的方向.【算法設(shè)計(jì)】本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序,實(shí)現(xiàn)手動(dòng)或者自動(dòng)生成一個(gè)nxm矩陣的迷宮,尋找一條從入口點(diǎn)到出口點(diǎn)的通路.我們將其簡(jiǎn)化成具體實(shí)驗(yàn)內(nèi)容如下：選擇手動(dòng)或者自動(dòng)生成一個(gè)nxm的迷宮,將迷宮的左上角作入口,右下角作出口,設(shè)“0為通路,“1為障礙,即

2、無(wú)法穿越.假設(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)迷宮抽象

3、數(shù)據(jù)類型.【源代碼】#include<stdlib.h> /庫(kù)中包含 system("pause")和 rand()函數(shù)#include<stdio.h> /c語(yǔ)言里的庫(kù)#include<iostream>#include <malloc.h>#define ERROR 0 #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define M 49#define N 49using namespace std;int mazeMN;ty

4、pedef int Status;typedef structint m,n,direc;MazeType,*LMazeType;typedef structLMazeType 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(

5、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);自動(dòng)生成迷宮void Init_automatic_Maze(int mazeMN,int m,int n)/int i,j;cout<<"n 迷宮生成中nn"system("pause

6、");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<<""elsecout<<""cout<<endl;Statu

7、s 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+STACKINCREME

8、NT) * 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

9、=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.d

10、irec=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

11、.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;cout<<"break; case 10:

12、cout<<"break; case 11:cout<<"Jbreak; case 12:cout<<"一break; case 13:cout<<"Tbreak; ) ) cout<<endl; )cout<<"入口 "<<endl; cout<<"完成!"<<endl;return OK;)int main()int i,m,n,mazeMN,cycle=0; while(cycle!=(-1) cout

13、<<" i*n"cout<<"歡迎進(jìn)入迷宮求解系統(tǒng)n"cout<<endl;cout<<" *cout<<"1手動(dòng)生成迷宮»,；cout<<"2自動(dòng)生成迷宮»,；cout<<"3退出nn"cout<<"I*ncout<<"n"cout<<"請(qǐng)選擇你的操作：n"cin>>i;switch(i)case 1:c

14、out<<"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è)范圍(1-49,1-49),請(qǐng)重新輸入：nn"cout<<"n 請(qǐng)輸入行數(shù)："cin>>m;cout<<"n"cout<<"請(qǐng)輸入列數(shù)：&

15、quot;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<<"尋找路徑."<<e

16、ndl;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&q

17、uot;cout<<" 請(qǐng)輸入列數(shù)："cin>>n;while(m<0|m>49)|(n<0|n>49)(cout<<"n抱歉,你輸入的行列數(shù)超出預(yù)設(shè)范圍(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);PrintMaz

18、e(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é)