迷宫解题
迷宫解题是我最喜欢的栈的实际应用，可以用来做一些外挂，具体什么外挂？呵呵。。自己好好想想。
这个迷宫能走出来吗？我想99.999%的人都能够解出来。用笔沿着空白处画，路不通折回去再走下一条路，直到出口处。这里我们用的是穷举法，但是如何让计算机按照我们的思维进行路径选择呢？这就可以用到我们的栈结构了。栈能够依次保留你所经过的路径，并能够遇到死胡同后按照原路返回。
下边就说一下思路。
- 如何判定方向？ 从入口位置按照固定的方向行走，比如约定第一步向左，如果不通，则向下，不通再向右，不通最后向上。这样就可以定义4个数值分别为1、2、3、4，分别代表左、下、右、上。这个顺序你自己可以定义，只要在程序中按照你规定的方向实现就行。
- 怎么判断遇到障碍物或者已经走过的线路？ 这个问题就是核心问题了。我用一个二维数组来模拟迷宫，约定数字1位障碍物，数字0位道路，数字2位已经通过的路径，数字3表示已经无路可走的路径。
- 栈在迷宫解题中怎么应用？ 这个问题是不少初学者疑惑的，简单的栈会用，但是灵活一点就不知道该如何使用了。压栈是将可以通过的路径的信息保存到栈中。那什么时候弹栈呢？就是遇到障碍物或者已经走过的路径。
- 怎么判断是死胡同呢？ 这个就是很巧妙的运用到栈元素结构中的方向字段，如果4个方向都不能通行，则判定为死路一条。将栈顶元素弹出来，改变个方向，再压入，循环到4个方向都不通时，倒着将坐标对应数值改为3，并且弹栈。如果弹出的元素方向信息不为4，则接着找，否则接着弹栈。
下边通过实际代码详细讲一下。
- 数据机构的变化
为了能够符合解题思路，需要创建一个新的结构，而且这个结构中应当包含位置、方向、步骤信息。将原来sqstack.h中的SElemType 定义修改成下边的代码。
typedef struct
{
int x; //坐标x
int y; //坐标y
} PosType;
typedef struct
{
int ord; //步骤
PosType seat; //坐标信息
int di; //方向
} SElemType;
- 模拟迷宫
如何让计算机知道哪些是障碍物，哪些能够通过，我这里用一个二维数组进行模拟。
void Init_Maze(int* s)
{
int i,j;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
*(s + i * 10 + j) = 0;
}
}
for (i = 0; i < 10; i++)
{
*(s + i) = 1; //第一行
*(s + 9 * 10 + i) = 1;//第10行
*(s + i * 10) = 1; //第一列
*(s + i * 10 + 9) = 1; //最后一列
}
//其他零星数据块
*(s + 10 + 3) = 1; *(s + 10 + 7) = 1;
*(s + 20 + 3) = 1; *(s + 20 + 7) = 1;
*(s + 30 + 5) = 1; *(s + 30 + 6) = 1;
*(s + 40 + 2) = 1; *(s + 40 + 3) = 1; *(s + 40 + 4) = 1;
*(s + 50 + 4) = 1;
*(s + 60 + 2) = 1; *(s + 60 + 6) = 1;
*(s + 70 + 2) = 1; *(s + 70 + 3) = 1; *(s + 70 + 4) = 1; *(s + 70 + 6) = 1; *(s + 70 + 7) = 1;
*(s + 80 + 1) = 1;
Print_Maze(s);
}
效果是什么呢？
怎么样，和上边的迷宫差不多一致。看看求出的路径是怎么样的。
数字2代表着线路，数字3则代表的是死胡同。我把步骤也打印出来。
- 核心代码
通过穷举法视图将说有的路径找到，知道找到出口为止。
Status MazePath()
{
/*
迷宫类型：1 为墙体
0 为未到过
2 为已经到
3 为此路不通
*/
int maze[10][10];
SqStack sstack;
PosType start, end,curpos;
int user_step = 0;
SElemType cur_e;
SElemType* le=NULL;
SElemType* ll = NULL;
int n=0;
printf("初始化迷宫：\n");
Init_Maze(maze);
Init_Stack(&sstack);
//起始坐标
start.x = 1;
start.y = 1;
//出口坐标
end.x = 8;
end.y = 8;
curpos.x = start.x;
curpos.y = start.y;
user_step = 1;
do
{
if (Pass(maze, &curpos)) //判断此节点是否到过，如果对应数组中为0，则说明可以通过
{
FootPrint(maze, &curpos);//标记已经到过，标记为2
cur_e.ord = user_step;
cur_e.seat = curpos;
cur_e.di = 1;
Push(&sstack,cur_e); //压栈，保存当前信息
if (curpos.x == end.x && curpos.y == end.y) //判定是否到达出口
{
break; //到达出口跳出循环
}
curpos = NextPos(&curpos,1); //获取下一个位置，位置改变取决于第二个方向参数
user_step++; //步数增加
}
else
{
if (!IsStackEmpty(&sstack)) //下一个位置不能通过
{ //将栈顶元素弹出来，改变个方向，再压入，循环到4个方向都不通时
//倒着将坐标对应数值改为3，并且弹栈。
//如果弹出的元素方向信息不为4，则接着找，否则接着退出。
Pop(&sstack, &cur_e);
while (cur_e.di == 4 && !IsStackEmpty(&sstack))
{
MarkFlag(maze, &cur_e.seat);
Pop(&sstack, &cur_e);
}
if (cur_e.di < 4)
{
cur_e.di++; //换个方向
Push(&sstack, cur_e);
curpos = NextPos(&cur_e.seat, cur_e.di);
}
}
}
} while (!IsStackEmpty(&sstack));
printf("-------------------------------\n");
printf("迷宫路径：\n");
Print_Maze(maze);
printf("-------------------------------\n");
printf("打印迷宫路径：\n");
///打印步骤
le = (SElemType*)malloc(sizeof(SElemType) * 1024);
ll = le;
while (!IsStackEmpty(&sstack))
{
Pop(&sstack, &cur_e);
*le = cur_e;
le++;
n++;
}
le--;
while (n>0)
{
printf("第%d步：x=%d,y=%d\n", (*le).ord, (*le).seat.x, (*le).seat.y);
n--;
le--;
}
//printf("%c\n", *ll);
free(ll);
///
DestoryStack(&sstack);
return OK;
}
- 完整代码
#include<stdio.h>
#include<stdlib.h>
#include"sqstack.h"
void Print_Maze(int* s)
{
int i, j;
//打印迷宫
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
printf("%d ", *(s + i * 10 + j));
}
printf("\n");
}
}
void Init_Maze(int* s)
{
int i,j;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
*(s + i * 10 + j) = 0;
}
}
for (i = 0; i < 10; i++)
{
*(s + i) = 1; //第一行
*(s + 9 * 10 + i) = 1;//第10行
*(s + i * 10) = 1; //第一列
*(s + i * 10 + 9) = 1; //最后一列
}
//其他零星数据块
*(s + 10 + 3) = 1; *(s + 10 + 7) = 1;
*(s + 20 + 3) = 1; *(s + 20 + 7) = 1;
*(s + 30 + 5) = 1; *(s + 30 + 6) = 1;
*(s + 40 + 2) = 1; *(s + 40 + 3) = 1; *(s + 40 + 4) = 1;
*(s + 50 + 4) = 1;
*(s + 60 + 2) = 1; *(s + 60 + 6) = 1;
*(s + 70 + 2) = 1; *(s + 70 + 3) = 1; *(s + 70 + 4) = 1; *(s + 70 + 6) = 1; *(s + 70 + 7) = 1;
*(s + 80 + 1) = 1;
Print_Maze(s);
}
int Pass(int* maze,PosType* p)
{
//判断p对应的位置是否有来到过
if (*(maze + p->y * 10 + p->x) == 0)
{
return 1;
}
else
{
return 0;
}
}
void FootPrint(int* maze, PosType* p)
{
*(maze + p->y * 10 + p->x) = 2;
}
void MarkFlag(int* maze, PosType* p)
{
*(maze + p->y * 10 + p->x) = 3;
}
PosType NextPos(PosType* p,int di)
{
switch (di)
{
case 1:
p->x += 1;
break;
case 2:
p->y += 1;
break;
case 3:
p->x -= 1;
break;
case 4:
p->y -= 1;
break;
default:
break;
}
return *p;
}
Status MazePath()
{
/*
迷宫类型：1 为墙体
0 为未到过
2 为已经到
3 为此路不通
*/
int maze[10][10];
SqStack sstack;
PosType start, end,curpos;
int user_step = 0;
SElemType cur_e;
SElemType* le=NULL;
SElemType* ll = NULL;
int n=0;
printf("初始化迷宫：\n");
Init_Maze(maze);
Init_Stack(&sstack);
//起始坐标
start.x = 1;
start.y = 1;
//出口坐标
end.x = 8;
end.y = 8;
curpos.x = start.x;
curpos.y = start.y;
user_step = 1;
do
{
if (Pass(maze, &curpos)) //判断此节点是否到过
{
FootPrint(maze, &curpos);//标记已经到过
cur_e.ord = user_step;
cur_e.seat = curpos;
cur_e.di = 1;
Push(&sstack,cur_e);
if (curpos.x == end.x && curpos.y == end.y)
{
break; //到达出口跳出循环
}
curpos = NextPos(&curpos,1);
user_step++;
}
else
{
if (!IsStackEmpty(&sstack))
{
Pop(&sstack, &cur_e);
while (cur_e.di == 4 && !IsStackEmpty(&sstack))
{
MarkFlag(maze, &cur_e.seat);
Pop(&sstack, &cur_e);
}
if (cur_e.di < 4)
{
cur_e.di++; //换个方向
Push(&sstack, cur_e);
curpos = NextPos(&cur_e.seat, cur_e.di);
}
}
}
} while (!IsStackEmpty(&sstack));
printf("-------------------------------\n");
printf("迷宫路径：\n");
Print_Maze(maze);
printf("-------------------------------\n");
printf("打印迷宫路径：\n");
///打印步骤
le = (SElemType*)malloc(sizeof(SElemType) * 1024);
ll = le;
while (!IsStackEmpty(&sstack))
{
Pop(&sstack, &cur_e);
*le = cur_e;
le++;
n++;
}
le--;
while (n>0)
{
printf("第%d步：x=%d,y=%d\n", (*le).ord, (*le).seat.x, (*le).seat.y);
n--;
le--;
}
//printf("%c\n", *ll);
free(ll);
///
DestoryStack(&sstack);
return OK;
}
int main()
{
MazePath();
system("pause");
}
转载自原文链接, 如需删除请联系管理员。
原文链接：（十三）栈的应用 --- 迷宫解题五行八卦阵，转载请注明来源！