#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define M 4
#define N 4
/*
迷宫--- 外围加上一圈 1
起点--0 0 1 1
0 0 0 0
0 1 1 1
0 0 0 0--出口
*/
//此迷宫按照优先向右下方向移动的标准！！！！
//要用链表形式的栈存放坐标+方向
typedef struct {
//存放坐标x,y 接下来的前进方向di
int x;
int y;
int di;
}Pos;
//定义一个栈
typedef struct {
Pos* top;
Pos* base;
}Stack;
//栈的初始化
int InitStack(Stack& s) {
s.base = new Pos[MAXSIZE];
s.top = s.base;
return 0;
}
//入栈
int Push(Stack& s,Pos n) {
if (s.top - s.base == MAXSIZE)
{
printf("栈满\n");
return 0;
}
else
{
*s.top++ = n;
}
return 0;
}
//出栈
int Pop(Stack& s, Pos& e) {
if (s.top == s.base )
{
printf("栈空\n");
return 0;
}
else
{
e = *--s.top;
}
return 0;
}
//从栈底输出栈
int printStack(Stack& s) {
Stack p;
//int i = 0;
p.base = s.base;
p.top = s.top;
while (p.base != p.top)
{
printf("(%d,%d)\n",p.base[0].x,p.base[0].y);
p.base++;
}
return 0;
}
//方向试探
typedef struct {
//x,y方向上的增量
int incX, incY;
}Direction;
//0 -3 依次表示向右 下 左 上 移动
Direction direction[4]{{0,1} ,{1,0},{0,-1},{-1,0} };
//栈中的数据元素
typedef struct {
//当前访问迷宫各自的横纵坐标
int x, y;
int di;//当前方向 di = 0 1 2 3
}Box;
//方法， 当到达某点(i,j)后,将对应的maze(i,j) 置为-1，其他未经过的点只能是1/0；
bool findPath(int maze[M + 2][N + 2], Direction direct[], Stack& s) {
Pos temp;
int x, y, di;//迷宫格子当前的纵横坐标和方向
int line, col;//迷宫下一组单元的行列坐标
maze[1][1] = -1;
temp = { 1,1,-1 };
//压栈
Push(s, temp);
while (s.base != s.top)
{
//出栈
Pop(s,temp);
x = temp.x;
y = temp.y;
di = temp.di + 1;
while (di < 4)
{
line = x + direct[di].incX;
col = y + direct[di].incY;
if (maze[line][col] == 0) {
temp = { x,y,di };
Push(s, temp);
//将走过的格子赋值为-1
x = line; y = col; maze[line][col] = -1;
if (x == M&&y == N )
{
printf("成功走出迷宫！\n");
//输出路线 + 出口
printStack(s);
printf("(4,4)\n");
return true;
}
else
{
di = 0;
}
}
else
{
di++;
}
}
}
return false;//迷宫没有出口
}
int main() {
//初始化栈
Stack s;
InitStack(s);
int inner[M][N] = { {0,0,1,1},{0,0,0,0},{0,1,1,1},{0,0,0,0} };
int maze[M + 2][N + 2];
// 初始化迷宫
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
maze[i + 1][j + 1] = inner[i][j];
}
}
for (int i = 0; i < M+2; i++)
{
maze[i][0] = 1;
maze[i][N+1] = 1;
}
for (int i = 0; i < N+2; i++)
{
maze[0][i] = 1;
maze[M + 1][i] = 1;
}
printf("迷宫为：\n");
for (int i = 0; i < M + 2; i++)
{
for (int j = 0; j < N + 2; j++) {
printf("%d\t", maze[i][j]);
};
printf("\n");
};
findPath(maze, direction, s);
return 0;
}