走迷宫(栈实现)(c++实现)

这是数据结构老师的一道例题，具体的话：先生成一个15*15的矩阵，起点在矩阵的左上角，终点在矩阵的右下角，问是否能走出迷宫，如果可以的话，输出迷宫路径。

代码实现：

#include"pch.h"
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<cstdio>
using namespace std;

//生成迷宫
const int HEIGHT = 15;
const int WIDTH = 15;
int maze[HEIGHT][WIDTH];
void initialMaze()
{
	maze[0][0] = 0;//入口
	maze[HEIGHT - 1][WIDTH - 1] = 0;//出口
	for (int i = 0; i < HEIGHT; i++)//用随机数0,1填充迷宫
	{
		for (int j = 0; j < WIDTH; j++)
		{
			if (i == 0 && j == 0)
				continue;
			if (i == HEIGHT - 1 && j == WIDTH - 1)
				continue;
			maze[i][j] = rand() % 2;
		}
	}
	//展示生成的迷宫
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			cout << maze[i][j];
			if (j != WIDTH - 1)
			{
				cout << " ";
			}
			else
			{
				cout << endl;
			}
		}
	}
}
//生成方向
int directory[8][2] = { {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
//判断是否越界
bool isLeap(int x, int y)
{
	return x >= 0 && x < WIDTH&&y >= 0 && y < HEIGHT;

}
//任意位置的结构体
struct point {
	int x;
	int y;
};
//声明用于存储路径的结构体
struct dir
{
	int x;
	int y;
	int d;
};
//声明用于存储路径的栈
stack<dir> directoryStack;
//迷宫循迹
void mazeTravel(point start, point end, int maze[HEIGHT][WIDTH], int directory[8][2])
{
	stack<dir> s;
	dir element, e;
	int i;
	int j;
	int d;
	int a;
	int b;
	maze[start.x][start.y] = 2;//首先在起点做上标记
	element.x = start.x;//第一个方向
	element.y = start.y;
	element.d = -1;
	directoryStack.push(element);
	while (!directoryStack.empty())//当栈不空，有路径可走时
	{
		element = directoryStack.top();
		directoryStack.pop();
		i = element.x;
		j = element.y;
		d = element.d + 1;
		while (d < 8)
		{
			a = i + directory[d][0];//预计的下一个点的位置
			b = j + directory[d][1];
			if (a == end.x&&b == end.y&&maze[a][b] == 0)//当我们找到了出口
			{
				element.x = i;//将原有元素入栈
			
	element.y = j;
				element.d = d;//更改了原有元素的方向指向
				directoryStack.push(element);
				element.x = a;
				element.y = b;
				element.d = 886;
				directoryStack.push(element);//将出口的信息入栈
				printf_s("\n0=东 1=东南 2=南 3=西南 4=西 5=西北 6=北 7=东北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
				while (!directoryStack.empty())//逆转序列输出迷宫路径序列
				{
					dir temp = directoryStack.top();
					directoryStack.pop();
					s.push(temp);
				}
				while (!s.empty())
				{
					dir temp = s.top();
					s.pop();
					printf_s("-->(%d,%d,%d)", temp.x, temp.y, temp.d);
				}
				return;
			}
			if (isLeap(a, b))
			{
				if (maze[a][b] == 0)
				{
					maze[a][b] = 2;
					element.x = i;
					element.y = j;
					element.d = d;
					directoryStack.push(element);
					i = a;
					j = b;
					d = -1;
				}
			}
			d++;
		}
	}
	printf_s("没有找到可以走出此迷宫的路径\n");
}
int main()
{
	srand(time(0));
	initialMaze();
	point a, b;
	a.x = 0;
	a.y = 0;
	b.x = HEIGHT - 1;
	b.y = WIDTH - 1;
	mazeTravel(a, b, maze, directory);
	return 0;
}

结果展示：