本文采用C语言应用顺序栈实现对迷宫问题的求解（走迷宫其实也蛮有意思的）
【问题描述】
采用“穷举求解”方法，从起点出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索。为了保证在任何位置上都能沿原路返回，需要用一个后进先出的顺序栈结构来保存从起点到当前位置的路径。
迷宫如图所示（代码中也可以自己更改）：
迷宫
(代码中'#'表示墙壁，‘ ’代表可以通过)
【算法思想】
迷宫求解
假设“当前位置”指的是”在搜索过程中某一时刻所在迷宫图中的某个方块的位置“，则求迷宫的一条路径的算法的基本思想可为：
1.若当前位置”可通“，则纳入”当前路径”，并继续朝”下一位置探索“，即切换”下一位置“为”当前位置“，如此重复直到到达出口；
2.若当前位置”不可通“，则应顺着”来向“退回到”前一通道块“。然后朝着除”来向“之外的其他方向继续探索；
3.若该通道块的四周方块均”不可通“，则应从”当前路径“上删除该通道块。
所谓”下一位置“指的是”当前位置“的四周4个方向上(东、南、西、北)相邻的方块。假设以栈S记录”当前路径“，则栈顶存放的是”当前路径上最后一个通道块“，由此，”纳入路径“的操作即为”当前位置入栈“；”从当前路径上删除前一通道块“的操作即为”出栈“。
算法思想
下面首先来熟悉一下栈的实现，
top为指向栈顶元素的下一位置的指针，base为指向栈底元素的指针
一、栈类型的定义：
typedef struct
{
SElemType *top;
SElemType *base;
int stacksize;
}Stack;
二、栈的相关操作
1、栈的初始化
//栈初始化
void InitStack(Stack **b)
{
(*b)->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));
if (!b) exit(OVERFLOW);
(*b)->top = (*b)->base;
(*b)->stacksize = MAXSIZE;
}
2、判断栈空
//栈空
Status StackEmpty(Stack *b)
{
if (b->top == b->base)
{
return OK;
}
else
{
return ERROR;
}
}
3、判断栈满
//栈满
Status StackFull(Stack *b)
{
if (((b->top) - (b->base)) >= b->stacksize)
{
return OK;
}
else
{
return ERROR;
}
}
4、入栈
//入栈
void Push(Stack **b, SElemType e)
{
if (StackFull(*b))
{
exit(OVERFLOW);
}
*(*b)->top = e;
(*b)->top = (*b)->top + 1;
}
5、出栈
//出栈
void Pop(Stack **b, SElemType *e)
{
if (StackEmpty(*b))
{
exit(ERROR);
}
(*b)->top = (*b)->top - 1;
*e = *(*b)->top;
}
三、定义地图
//地图，‘#’指墙壁
char map[MAPROW + 2][MAPCOL + 2] = {
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
//迷宫中的坐标位置
typedef struct pos
{
int x;
int y;
}pos;
typedef struct current
{
pos seat;//当前位置
int direction;//走向下一通道块的方向，顺时针方向：direction=1,2,3,4分别为东，南，西，北
}current;
typedef current SElemType;
pos start = { 1,1 };//设置迷宫起点
pos end = { MAPROW,MAPCOL };//设置迷宫终点
四、实现迷宫相应操作
1、对曾经经过的路径设置标记‘1',方便寻找最短路径
//对曾经经过的路径设置标记`‘1'`,方便寻找最短路径
void beforesign(pos curpos)
{
map[curpos.x][curpos.y] = '1';
}
2、对于曾经走过虽不是墙壁但是不通的路，标记'@'
//对于曾经走过虽不是墙壁但是不通的路，标记'@'
void nosign(pos curpos)
{
map[curpos.x][curpos.y] = '@';
}
3、返回下一位置坐标
方向
//返回下一位置坐标
pos nextpos(pos curpos, int dir)
{
switch (dir)
{
case 1://向东走，行号不变，列号加一
curpos.y = curpos.y + 1;
break;
case 2://向南走
curpos.x = curpos.x + 1;
break;
case 3://向西走
curpos.y = curpos.y - 1;
break;
case 4://向北走
curpos.x = curpos.x - 1;
break;
}
return curpos;
}
4、判断当前位置是否可通过，即为' ',而不是'#'墙，‘@’死路，‘1’已走过
//判断当前位置是否可通过，即为' ',而不是'#'墙，‘@’死路，‘1’已走过
bool pass(pos curpos)
{
if (map[curpos.x][curpos.y] == ' ')
{
return true;
}
else
{
return false;
}
}
5、看迷宫中是否存在一条从入口到出口的路，存放在栈中
注意使用结构体前一定要分配空间，即
Stack *s; s = (Stack*)malloc(sizeof(Stack));
//看迷宫中是否存在一条从入口到出口的路，存放在栈中
bool path(pos start,pos end)
{
Stack *s;
s = (Stack*)malloc(sizeof(Stack));
InitStack(&s);
pos curpos = start;//设置当前位置为入口
if (pass(curpos))//如果该位置可以通过
{
beforesign(curpos);//作标记‘#’
current cur;
cur.seat = curpos;
cur.direction = 1;
Push(&s, cur);//将当前的方向和位置压栈
curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
}
while (!StackEmpty(s))
{
if (pass(curpos))//如果该位置可以通过
{
beforesign(curpos);//作标记‘#’
current cur;
cur.seat = curpos;
cur.direction = 1;
Push(&s, cur);//将当前的方向和位置压栈
if ((curpos.x == end.x) && (curpos.y == end.y))//到达终点停止
{
return true;
}
curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
}
else//如果该位置不能通过,则栈顶元素出栈，即刚刚走过的迷宫块退出
{
current cur;
Pop(&s, &cur);//弹出栈顶元素，并将该元素存在cur中
while ((cur.direction == 4) && (!StackEmpty(s)))
{
nosign(cur.seat);//标记该块四周均不可通
Pop(&s, &cur);//继续弹出上一块的栈顶位置（即上一步的位置），存在cur中
}
if (cur.direction < 4)//如果弹出的当前位置还有别的方向没有探索，则继续探索
{
cur.direction = cur.direction + 1;//试探下一个方向
Push(&s, cur);//将该方向的位置压入栈中
curpos = nextpos(cur.seat, cur.direction);//计算在该方向的下一位置
}
}
}
return false;
}
四、输出地图相关函数
1、打印迷宫
//打印迷宫
void printmap()
{
for (int i = 0; i < MAPROW + 2; i++)
{
for (int j = 0; j < MAPCOL + 2; j++)
{
printf("%c", map[i][j]);//打印完整的迷宫
}
printf("\n");
}
printf("\n");
}
2、仅打印通过迷宫的路径
//仅打印通过迷宫的路径
void printpath()
{
for (int i = 0; i < MAPROW + 2; i++)
{
for (int j = 0; j < MAPCOL + 2; j++)
{
if ((map[i][j] == '#') || (map[i][j] == '1'))//仅打印墙壁和走过的迷宫路径
{
printf("%c", map[i][j]);
}
else
{
printf(" ");
}
}
printf("\n");
}
printf("\n");
}
五、main函数测试
int main()
{
printf("迷宫的初始状态为：\n");
printmap();
if (path(start, end))//如果有路径
{
printf("迷宫有路径可通过\n");
printf("迷宫标识后的状态为：\n");
printmap();
printf("通过迷宫的路径为：\n");
printpath();
}
else
{
printf("迷宫不存在可通过的路径\n");
}
return 0;
}
六、程序运行结果
（1）
（2）
（3）
七、完整代码（附注释）
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAPROW 8
#define MAPCOL 8
typedef int Status;
//迷宫中的坐标位置
typedef struct pos
{
int x;
int y;
}pos;
typedef struct current
{
pos seat;//当前位置
int direction;//走向下一通道块的方向，顺时针方向：direction=1,2,3,4分别为东，南，西，北
}current;
typedef current SElemType;
typedef struct
{
SElemType *top;
SElemType *base;
int stacksize;
}Stack;
//栈初始化
void InitStack(Stack **b)
{
(*b)->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));
if (!b) exit(OVERFLOW);
(*b)->top = (*b)->base;
(*b)->stacksize = MAXSIZE;
}
//栈空
Status StackEmpty(Stack *b)
{
if (b->top == b->base)
{
return OK;
}
else
{
return ERROR;
}
}
//栈满
Status StackFull(Stack *b)
{
if (((b->top) - (b->base)) >= b->stacksize)
{
return OK;
}
else
{
return ERROR;
}
}
//入栈
void Push(Stack **b, SElemType e)
{
if (StackFull(*b))
{
exit(OVERFLOW);
}
*(*b)->top = e;
(*b)->top = (*b)->top + 1;
}
//出栈
void Pop(Stack **b, SElemType *e)
{
if (StackEmpty(*b))
{
exit(ERROR);
}
(*b)->top = (*b)->top - 1;
*e = *(*b)->top;
}
//地图，‘#’指墙壁
char map[MAPROW + 2][MAPCOL + 2] = {
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
pos start = { 1,1 };//设置迷宫起点
pos end = { MAPROW,MAPCOL };//设置迷宫终点
//对曾经经过的路径设置标记‘1',方便寻找最短路径
void beforesign(pos curpos)
{
map[curpos.x][curpos.y] = '1';
}
//对于曾经走过虽不是墙壁但是不通的路，标记'@'
void nosign(pos curpos)
{
map[curpos.x][curpos.y] = '@';
}
//返回下一位置坐标
pos nextpos(pos curpos, int dir)
{
switch (dir)
{
case 1://向东走，行号不变，列号加一
curpos.y = curpos.y + 1;
break;
case 2://向南走
curpos.x = curpos.x + 1;
break;
case 3://向西走
curpos.y = curpos.y - 1;
break;
case 4://向北走
curpos.x = curpos.x - 1;
break;
}
return curpos;
}
//判断当前位置是否可通过，即为' ',而不是'#'墙，‘@’死路，‘1’已走过
bool pass(pos curpos)
{
if (map[curpos.x][curpos.y] == ' ')
{
return true;
}
else
{
return false;
}
}
//看迷宫中是否存在一条从入口到出口的路，存放在栈中
bool path(pos start,pos end)
{
Stack *s;
s = (Stack*)malloc(sizeof(Stack));
InitStack(&s);
pos curpos = start;//设置当前位置为入口
if (pass(curpos))//如果该位置可以通过
{
beforesign(curpos);//作标记‘#’
current cur;
cur.seat = curpos;
cur.direction = 1;
Push(&s, cur);//将当前的方向和位置压栈
curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
}
while (!StackEmpty(s))
{
if (pass(curpos))//如果该位置可以通过
{
beforesign(curpos);//作标记‘#’
current cur;
cur.seat = curpos;
cur.direction = 1;
Push(&s, cur);//将当前的方向和位置压栈
if ((curpos.x == end.x) && (curpos.y == end.y))//到达终点停止
{
return true;
}
curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
}
else//如果该位置不能通过,则栈顶元素出栈，即刚刚走过的迷宫块退出
{
current cur;
Pop(&s, &cur);//弹出栈顶元素，并将该元素存在cur中
while ((cur.direction == 4) && (!StackEmpty(s)))
{
nosign(cur.seat);//标记该块四周均不可通
Pop(&s, &cur);//继续弹出上一块的栈顶位置（即上一步的位置），存在cur中
}
if (cur.direction < 4)//如果弹出的当前位置还有别的方向没有探索，则继续探索
{
cur.direction = cur.direction + 1;//试探下一个方向
Push(&s, cur);//将该方向的位置压入栈中
curpos = nextpos(cur.seat, cur.direction);//计算在该方向的下一位置
}
}
}
return false;
}
//打印迷宫
void printmap()
{
for (int i = 0; i < MAPROW + 2; i++)
{
for (int j = 0; j < MAPCOL + 2; j++)
{
printf("%c", map[i][j]);//打印完整的迷宫
}
printf("\n");
}
printf("\n");
}
//仅打印通过迷宫的路径
void printpath()
{
for (int i = 0; i < MAPROW + 2; i++)
{
for (int j = 0; j < MAPCOL + 2; j++)
{
if ((map[i][j] == '#') || (map[i][j] == '1'))//仅打印墙壁和走过的迷宫路径
{
printf("%c", map[i][j]);
}
else
{
printf(" ");
}
}
printf("\n");
}
printf("\n");
}
int main()
{
printf("迷宫的初始状态为：\n");
printmap();
if (path(start, end))//如果有路径
{
printf("迷宫有路径可通过\n");
printf("迷宫标识后的状态为：\n");
printmap();
printf("通过迷宫的路径为：\n");
printpath();
}
else
{
printf("迷宫不存在可通过的路径\n");
}
return 0;
}
越努力，越幸运
end~~~
