#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include<stdbool.h> //c语言和c++中对bool的定义不同,由于在c++工程中使用的是c语言,所以无法通过,也可以写成 _Bool ,这个是c++的定义方式
//顺序栈:sequential stack
#define MaxSize 100
typedef struct
{
int data[MaxSize];
int top;//栈顶指针
}SQStack; //定义栈
inline bool InitStack(SQStack* s)
{
s = (SQStack*)malloc(sizeof(SQStack));
if (s == NULL) //如果申请失败,返回“假”
return false;
s->top = -1; //此时栈内无元素
return true;
} //初始化栈
inline void DestroyStack(SQStack* s)
{
free(s);
} //销毁栈
inline bool StackEmpty(SQStack* s)
{
return (s->top == -1);
} //判断栈是否为空
inline bool Push(SQStack* s, int e)
{
if (s->top == MaxSize - 1 )
return false;
s->top++;
s->data[s->top] = e;
return true;
} //进栈
inline bool Pop(SQStack* s, int e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
} //出栈
inline bool GetTop(SQStack* s, int e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
} //取顶
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include"shunxu-zhan.c"
#define M 4
#define N 4
int mg[M+2][N+2] =
{
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0.1,0.0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1},
}; //定义迷宫
typedef struct
{
int i, j, di;//行、列、方位号
}Box; //定义储存的行径路线
typedef struct
{
Box data[MaxSize];
int top;
}ZhanType; //初始化所用的栈
bool mgpath(int xi, int yi, int xe, int ye) //入口(xi,yi),出口(xe,ye)
{
Box path[MaxSize],*e= (Box*)malloc(sizeof(Box));
int i, j, di, dil=0, djl=0;
int k; //动态
bool step;
ZhanType* zt=(ZhanType*)malloc(sizeof(ZhanType));//定义栈
InitStack(zt);
e->i = xi;
e->j = yi;
e->di = -1; //设置e为入口
Push(zt, e); //入栈
mg[xi][yi] = -1;
//防止重复
while (!StackEmpty (zt))
{
GetTop(zt,e); //取顶
i = e->i;
j = e->j;
di = e->di; //传入入口的坐标
if (i == xe && j == ye)
{
printf("迷宫路径如下:\n");
k = 0;
while (!StackEmpty(zt))
{
Pop(zt, e); //出栈
path[k++] = *e;
}
while (k >= 1)
{
k--;
printf("\t(%d,%d),,%d", path[k].i, path[k].j, k);
if ((k + 1) % 5 == 0)
printf("\n");
}
printf("\n");
DestroyStack(zt);
return true;
}
step = false;
while (di < 4 && !step)
{
di++;
switch (di) //从上顺时针旋转
{
case0:dil = i - 1, djl = j;break; //上移
case1: dil= i , djl = j+1;break; //右移
case2:dil = i + 1, djl = j;break; //下移
case3:dil = i - 1, djl = j-1;break; //左移
}
if (mg[dil][djl] == 0)
step = true;
}
if (step)
{
zt->data[zt->top].di = di;
e->i = dil;
e->j = djl;
e->di = -1; //更新top坐标
Push(zt, e);
mg[dil][djl] = -1; //避免重复走
}
else
{
Pop(zt, e);
mg[e->i][e->j] = 0;
}
DestroyStack(zt);
return false;
}
}
main()
{
if (!mgpath(1, 1, M, N))
printf("无解");
return false;
}