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