讨论分别用堆栈和队列解决行走迷宫问题的方法(参加者:陈卓、毛敏磊) -2:
最编程
2024-06-29 21:16:15
...
对于迷宫问题用栈解决主要基于栈的特性Last in First Out(后进先出),可以很好的存储走迷宫时的中间状态——经过的路径。根据先进后出的特点可以大概想到看先将走过的路径存入栈内,当路走不通时将栈中的该路径弹出。同时根据迷宫的特点我们想到用二维数组来储存我们的迷宫。那么大概的思路便是遍历迷宫中的路径,将路径存入栈内,当所在路径没有新的路可走时开始回退也就是将栈内的元素弹出直到栈顶元素可以找到新的路径。
根据大概的思路先来定义会使用到的数据结构。
(1)对于迷宫中位置的存储定义一个数据结构,基于我们是用二维数组来存储迷宫,那么可以采用横坐标和纵坐标来描述位置。同时遍历路径我们需要一个能反映当前方向的变量所以有以下定义:
typedef struct
{
int x, y;
int di;//按照东南西北的顺序,di从1-4.
}Box;
(2)根据用横纵坐标来存储位置信息,可以使用横坐标和纵坐标的增减来表示移动因此可以定义一个结构数组来表示增减量所以有以下定义:
typedef struct
{
int x, y;//用x,y的增量来表示移动
}Direction;
Direction direct[5]{ {0,0},{1,0},{0,-1},{-1,0},{0,1} };//设定按东南西北的顺序来寻找出口
现在开始正式思考如何寻找迷宫的出口。首先找迷宫有两大步骤:1)在没路时能将栈内的元素弹出。2)能遍历迷宫能走的位置。那么我们可以设置双层循环嵌套,将遍历迷宫位置的步骤作为内层循环,弹出栈内元素作为外层循环。当遍历迷宫位置无路可走时退出内层循环进入外层循环将元素弹出直到有新的路径出现时。
同时对于走过的路径也应进行标记使系统能识别该位置走过,那么我们采用将走过的路的值赋为-1(用1表示迷宫的墙,0来表示可走的路)。
以下是代码的具体实现(栈):
#include<iostream>
#include<stack>
using namespace std;
typedef struct
{
int x, y; //用x,y的增量来表示移动
}Direction;
typedef struct
{
int x, y;
int di;
}Box1; //用来储存当前的位置和方向(栈)
int mg[1002][1002]; //定义一个存放迷宫的二维数组
int findPath(int M, int N);
int main()
{
int M, N, i, j;
cin >> M >> N;
for (i = 0; i < M + 2; i++)
{
mg[i][0] = 1;
mg[i][M + 1] = 1;
}
for (i = 0; i < N + 2; i++)
{
mg[0][i] = 1;
mg[M + 1][i] = 1;
}
for (i = 1; i < M + 1; i++)
{
for (j = 1; j < N + 1; j++)
{
cin >> mg[i][j];
}
} //将迷宫初始化,在外围建立一堵墙
findPath(M, N);
return 0;
}
int findPath(int M, int N)
{
Box1 temp;
stack<Box1> s;
int x, y, di;//存储当前地点的横坐标和纵坐标
int x1, y1;//存储下一个地点的横坐标和纵坐标
Direction direct[5]{ {0,0},{1,0},{0,-1},{-1,0},{0,1} };//设定按东南西北的顺序来寻找出口
mg[1][1] = -1;//将记过的地方设置为-1
temp = { 1,1,0 };
s.push(temp);//为循环同一先将入口存入栈内
while (!s.empty())
{
temp = s.top();
s.pop();
x = temp.x;
y = temp.y;
di = temp.di + 1;
while (di <= 4)//方向未尝试完
{
x1 = x + direct[di].x;
y1 = y + direct[di].y;
if (mg[x1][y1] == 0)
{
temp = { x,y,di };
s.push(temp);
x = x1;//移动到下一个地点
y = y1;
mg[x1][y1] = -1;
if (x == M && y == N)
{
cout << '(' << M << ',' << N << ')' << endl;
while (!s.empty())
{
cout << '(' << s.top().x << ',' << s.top().y << ')' << endl;
s.pop();
}
return 1;
}//迷宫有路
else {
di = 1;
}
}
else {
di++;
}
}
}
cout << "Not Found!";//返回0说明迷宫没有路
return 0;
}
运行结果如下
上一篇: 递归之迷宫问题
下一篇: 解决迷宫问题的回溯法