《數(shù)據(jù)結(jié)構(gòu) 迷宮求解》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) 迷宮求解（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
【完成題目3】迷宮求解
【問題描述】
以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。
【基本要求】
首先實現(xiàn)一個棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個坐標，d表示走到下一坐標的方向。
【算法設(shè)計】
本實驗的目的是設(shè)計一個程序，實現(xiàn)手動或者自動生成一個n×m矩陣的迷宮，尋找一條從入口點到出口點的通路。我們將其簡化成具體實驗內(nèi)容如下：
選擇手動或者自動生成一個n×m的迷宮，將迷宮的左上角作入口，右下角作出
2、口，設(shè)“0”為通路，“1”為障礙，即無法穿越。假設(shè)從起點出發(fā)，目的為右下角終點，可向“上、下、左、右、左上、左下、右上、右下”8個方向行走。如果迷宮可以走通，則用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宮的路徑。輸出迷宮原型圖、迷宮路線圖以及迷宮行走路徑。如果迷宮為死迷宮，輸出信息。
可以二維數(shù)組存儲迷宮數(shù)據(jù)，用戶指定入口下標和出口下標。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。
本程序包含三個模塊
1)主程序模塊：
void main()
{
初始化;
do {
接受命令
3、;
處理命令;
} while (命令! = 退出);
}
2)棧模塊——實現(xiàn)棧抽象數(shù)據(jù)類型；
3)迷宮模塊——實現(xiàn)迷宮抽象數(shù)據(jù)類型。
【源代碼】
#include //庫中包含system("pause")和rand()函數(shù)
#include //c語言里的庫
#include
#include
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKI
4、NCREMENT 10
#define OVERFLOW -1
#define M 49
#define N 49
using namespace std;
int maze[M][N];
typedef int Status;
typedef struct
{
int m,n,direc;
}MazeType,*LMazeType;
typedef struct
{
LMazeType top;
LMazeType base;
int stacksize;
int over;
}Stack;
void In
5、it_hand_Maze(int maze[M][N],int m,int n)
{
int i,j;
for(i=1;i<=m+1;i++)
for(j=1;j<=n+1;j++)
{
maze[i][j]=1;
}
cout<<"請按行輸入迷宮，0表示通路，1表示障礙:"<>maze[i][j];
for(i=1;i
6、
{
for(j=1;j
7、use");
for(i=1;i
8、[j]==1)
cout<<"■";
else
cout<<"□";
}
cout<
9、
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+=S
10、TACKINCREMENT;
}
*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 maze[M][N],int m,int n)
{
do
{
if(maze[e.m][e.n]==0)//0可通，1不可通，2為已走過
11、 {
Push(S,e);
maze[e.m][e.n]=2;
if(e.m==m&&e.n==n)
{
S.over=1;//表示存滿一條路徑
return OK;
}
else {
e.n++;
e.direc=0;//來這一點時的方向，0右1下2左3上
Maze
12、Path(S,e,maze,m,n);
}
}
else
{
if(S.top!=S.base&&S.over!=1)
{
switch(e.direc) //回到上一位置并同時改變方向走下一步
{
case 0:
e.n--;
e.m++;
13、 e.direc=1;
break;
case 1:
e.m--;
e.n--;
e.direc=2;
break;
case 2:
e.n++;
14、
e.m--;
e.direc=3;
break;
case 3:
Pop(S,e);
break;
}
}
}
}while(S.top!=S.base&&S.over!=1);
retur
15、n OK;
}
int PrintPath(Stack S,int maze[M][N],int row,int col)
{
if(S.top==S.base)
{
cout<<"\n===============================================\n";
cout<<"此迷宮無解\n\n";
return ERROR;
}
MazeType e;
while(S.top!=S.base)
{
16、
Pop(S,e);
maze[e.m][e.n]=(e.direc+10);
}
cout<<"完成!"<
17、
{
case 0:
cout<<"□";
break;
case 1:
cout<<"■";
break;
case 2:
cout<<"※";
break;
case 10:
18、 cout<<"→";
break;
case 11:
cout<<"↓";
break;
case 12:
cout<<"←";
break;
case 13:
cout<<"↑";
19、 break;
}
}
cout<
20、out<<"********************************************************************************\n";
cout<<" 歡迎進入迷宮求解系統(tǒng)\n";
cout<
21、 ☆ 1 手動生成迷宮 ☆\n";
cout<<" ☆ 2 自動生成迷宮 ☆\n";
cout<<" ☆ 3 退出 ☆\n\n";
cout<<"********************************************************************************\n";
cout<<"\n";
cout<<"請選擇你的操作：\n";
cin>>i;
22、 switch(i)
{
case 1:
cout<<"\n請輸入行數(shù)：";
cin>>m;
cout<<"\n";
cout<<"請輸入列數(shù)：";
cin>>n;
while((m<1||m>49)||(n<1||n>49))
{
cout<<"\n抱歉，你輸入的行列數(shù)超出預設(shè)范圍(1-49,1-49),請重新輸入：\n\n";
cout<<"\n請輸入行數(shù)：";
cin>>m;
cout<<"\n";
cout<<"請輸入列數(shù)：";
23、 cin>>n;
}
Init_hand_Maze(maze,m,n);
PrintMaze(maze,m,n);
MazeType start,end;
cout<<"請輸入起點m n:"<>start.m>>start.n;
start.direc=0;
cout<<"請輸入終點m n:"<>end.m>>end.n;
Stack S;
cout<<"尋找路徑..."<
24、itStack(S);
MazePath(S,start,maze,end.m,end.n);
PrintPath(S,maze,m,n);
system("pause");
cout<<"\n\nPress Enter Contiue!\n";
getchar();
while(getchar()!='\n'); //接受一個輸入，當為回車時執(zhí)行break跳出，否則一直執(zhí)行接受數(shù)據(jù)
break;
case 2:
cout<<"\n請輸入行數(shù)：";
25、cin>>m;
cout<<"\n";
cout<<"請輸入列數(shù)：";
cin>>n;
while((m<0||m>49)||(n<0||n>49))
{
cout<<"\n抱歉，你輸入的行列數(shù)超出預設(shè)范圍(0-49,0-49),請重新輸入：\n\n";
cout<<"\n請輸入行數(shù)：";
cin>>m;
cout<<"\n";
cout<<"請輸入列數(shù)：";
cin>>n;
}
Init_automatic_Maze(maze,m,n);
26、
PrintMaze(maze,m,n);
cout<<"請輸入起點m n:"<>start.m>>start.n;
start.direc=0;
cout<<"請輸入終點m n:"<>end.m>>end.n;
cout<<"尋找路徑..."<
27、maze,m,n);
system("pause");
cout<<"\n\nPress 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(ge
28、tchar()!='\n');
break;
}
}
}
【結(jié)果截圖】
迷宮無解的情況
手動生成迷宮的情況
自動生成迷宮的情況
【收獲及體會】
1. 本次實驗核心算法明晰，思路明確，易于實現(xiàn)。遇到的問題是，迷宮的外圍若未設(shè)置障礙，用此程序采用的求解迷宮路徑的算法無法獲得正確結(jié)果。
2. 本程序的MazePath算法代碼不夠簡潔，但不影響算法實現(xiàn)。
3. 本次實驗由于時間問題和知識水平有限，還存在一些問題，比如：界面比較單調(diào)，整個程序的功能還不完善，還有界面做的有些簡單，菜單沒有做好，可進行的操作太少，這些都有待進一步改善。
4．本次實驗使我對迷宮游戲的原理有了一定的了解，但做出的結(jié)果離真正的迷宮還有很大差距，還需要進一步完善，需要自己課下學習更多的知識。
數(shù)據(jù)結(jié)構(gòu) 迷宮求解
