讲解:
一、采用二维数组和srand函数随机生成只有0和1的迷宫。
二、求解迷宫大概思路:先将入口处的坐标即方向d入栈,然后当栈不为空时,取出栈顶(即当前节点)的数据。遍历当前节点的四个方向,找到可行的下一个节点,并将其入栈;如没有可行的下一个节点,则将当前节点值0(表示未走过),然后出栈,退回到前一个节点进行遍历。当栈顶数据和出口一致时,输出迷宫的通路。
#include <iostream>
#include <time.h>
#define M 100
#define N 100
#define MAXSIZE 100
using namespace std;
int maze[M][N];
void CreateMaze(int m, int n) //创建迷宫
{
srand(time(NULL));
for(int i=1;i<m+1;i++)
{
for(int j=1;j<n+1;j++)
{
maze[i][j] = rand()%2; //只有0和1的随机迷宫
}
}
maze[1][1] = -1; //直接入口置-1,表示可走
maze[m][n] = 0; //出口
for(int i=0;i<m+2;i++) maze[i][0] = 1; //设置围墙
for(int i=0;i<m+2;i++) maze[i][m+1] = 1;
for(int j=0;j<n+2;j++) maze[0][j] = 1;
for(int j=0;j<n+2;j++) maze[n+1][j] = 1;
}
void Print(int m,int n) //打印迷宫
{
for(int i=0;i<m+2;i++)
{
for(int j=0;j<n+2;j++)
{
if(maze[i][j] == 0)
cout << " ";
if(maze[i][j] == 1)
cout << "□";
}
cout << endl;
}
}
typedef struct //定义当前位置坐标
{
int x;
int y;
int d; //移动方向
}Point;
typedef struct //定义顺序栈
{
Point data[MAXSIZE]; //定义顺序栈的存储类型为结构体data
int top;
}SqStack;
bool MazePath(int x1,int y1,int m, int n)
{
int i,j,d,find;
SqStack S;
S.top = -1; //初始化栈
S.top++;
S.data[S.top].x = x1; S.data[S.top].y = y1; S.data[S.top].d = -1;
while(S.top>-1)
{
i = S.data[S.top].x; j = S.data[S.top].y; d = S.data[S.top].d;
if(i==m&&j==n)
{
cout << "找到路径:" << endl;
for(int i=0;i<m+2;i++)
{
for(int j=0;j<n+2;j++)
{
if(maze[i][j] == 1)
cout << "□";
else if(maze[i][j] == 0)
cout << " ";
else
cout << " *";
}
cout << endl;
}
return true;
}
find = 0; //设置标识,1表示找到下一个可行路径,0表示没有找到
while(d<4&&find==0) //遍历4个方向:0->东,1->南,2->西,3->北
{
d++;
switch(d)
{
case 0:
i = S.data[S.top].x+1; j = S.data[S.top].y; break;
case 1:
i = S.data[S.top].x; j = S.data[S.top].y+1; break;
case 2:
i = S.data[S.top].x-1; j = S.data[S.top].y; break;
case 3:
i = S.data[S.top].x; j = S.data[S.top].y-1; break;
}
if(maze[i][j] == 0) find = 1; //找到路径,标识置1,退出循环
}
if(find == 1) //找到路径
{
S.data[S.top].d = d; //记录当前节点往下一个节点的方向
S.top++; //下一个节点入栈
S.data[S.top].x = i;
S.data[S.top].y = j;
S.data[S.top].d = -1; //将下一个节点的走向置为-1
maze[i][j] = -1; //当前点置-1,表示走过
}
else //未找到路径
{
maze[S.data[S.top].x][S.data[S.top].y] = 0; //当前点置为0,表示未走过
S.top--; //出栈
}
}
return false;
}
int main()
{
int m,n;
int k=1;
while(k)
{
cin >> m >> n;
CreateMaze(m,n);
Print(m,n);
if(!MazePath(1,1,m,n))
{
cout << "找不到路径"<<endl;
k++;
}
else k=0;
}
}
运行结果:(由于随机生成大概率没有通路,所以输出较小的迷宫容易出结果)
文章来源:https://www.toymoban.com/news/detail-541832.html
写的很简陋,有不足之处请指正。文章来源地址https://www.toymoban.com/news/detail-541832.html
到了这里,关于数据结构——迷宫问题(顺序栈、C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!