简介
基于栈的迷宫问题本质上是深度优先遍历,从起点开始深度优先搜索,遇到碰壁的情况时,根据栈的特性,可以“回溯”到之前走过的路,并继续搜索未搜索的方向。
具体实现
我使用的ide是qt,它里面的一些图形库有助于我更加直观地理解深度优先搜索的过程。
我创建了迷宫类maze:
class maze
{
friend class widget;
protected:
int scale;//边长
int** data;
public:
maze(int s = 10):scale(s)
{
data = new int*[scale];
for(int i = 0;i <= scale - 1;++i)
{
data[i] = new int [scale];
}
}
~maze()
{
for(int i = 0;i <= scale - 1;++i)
{
delete [] data[i];
}
delete [] data;
}
int getScale() const{return scale;}
int** getData() const{return data;}//to be changed
void createMaze(const QString& cmd);//根据用户输入创建迷宫
void print() const;//在控制台输出
void findPath(QWidget* parent);//寻路,并在窗口中显示出来
};
迷宫的信息用一个scale*scale的二维数组存储,数组的值对应如下:
0:墙壁;1:空气;2:探测到的路;3:最终寻路的结果;4:无法走通的路
本文对应的迷宫如下,起点在左上角,终点在右下角。
寻路函数findPath传入参数QWidget* parent,方便对窗口进行图形化的绘制。
void maze::findPath(QWidget *parent)
{
struct dirPoint//数据包,存储一个位置和其访问方向的信息
{
int x;
int y;
int dir;
dirPoint(int xx,int yy,int d = 0):x(xx),y(yy),dir(d){}
};
stack<dirPoint> st;
dirPoint curPoint(0,0),lastPoint(0,0);//当前位置信息和上一个位置信息
bool isExplored;//标记一次探测是否成功
st.push(dirPoint(0,0));
while(!st.empty())
{
Sleep(20);
isExplored = false;
curPoint = st.top();
st.pop();
if(curPoint.dir == 4)//全部方向都已经被探索过
{
data[curPoint.x][curPoint.y] = 4;//设置为“失败点”
parent->repaint();
continue;
}
switch(curPoint.dir)
{
case 0:if(curPoint.x >= 1 && data[curPoint.x -1][curPoint.y] == 1)
{
lastPoint = curPoint;
--curPoint.x;
isExplored = true;
}break;//up
case 1:if(curPoint.x <= scale - 2 && data[curPoint.x + 1][curPoint.y] == 1)
{
lastPoint = curPoint;
++curPoint.x;
isExplored = true;
}break;//down
case 2:if(curPoint.y >= 1 && data[curPoint.x][curPoint.y - 1] == 1)
{
lastPoint = curPoint;
--curPoint.y;
isExplored = true;
}break;//left
case 3:if(curPoint.y <= scale - 2 && data[curPoint.x][curPoint.y + 1] == 1)
{
lastPoint = curPoint;
++curPoint.y;
isExplored = true;
}//right
default:break;
}
if(isExplored)
{
data[curPoint.x][curPoint.y] = 2;
parent->repaint();
++lastPoint.dir;
st.push(lastPoint);
curPoint.dir = 0;
st.push(curPoint);
}
else
{
++curPoint.dir;
st.push(curPoint);
}
if(curPoint.x == scale - 1 && curPoint.y == scale - 1)
{
break;
}
}
while(!st.empty())
{
curPoint = st.top();
st.pop();
data[curPoint.x][curPoint.y] = 3;
parent->repaint();
Sleep(20);
}
}
在函数findPath内,我写了一个包裹类,dirPoint,它有三个成员,x(行坐标),y(列坐标),dir(下一步要搜索的方向:0:上,1:下,2:左,3:右),用一个该类的栈进行深度优先搜索。同时,该函数使用bool型局部变量isExplored判断是否探路成功,该布尔值在每一次循环开始都被置为false。设置两个QPoint类的对象lastPoint和curPoint存储当前位置和上一位置。
初始时先将起点进栈,并将dir设为0,表示下一步要搜索的方向为上方。
显然上方此路不通,isExplored仍为false,于是将dir++,表示下一次搜索下方,并将该点进栈。
尝试了下、左都不行后,尝试向右行进,探路成功,isExplored变为true,并将当前位置赋值给lastPoint,同时dir++,curPoint更新为新探测到的位置,并将dir设为0(全新的点,四个方向都没有探测)。出switch语句后,由于isExplored变为true,依次将lastPoint和curPoint进栈。
由于规定路径不能重叠,已经走过的路会被视为“墙壁”,不允许返回探测,路径的回溯只依赖于栈的特点。
当弹出的一个点dir == 4时,表示四个方向已经探测完毕,此路必然不通,则continue,进入下一轮循环时,弹出的点必然是路径的上一个点,如果还有别的方向,则尝试该方向,如果仍然dir == 4,表示这个点也走进了死胡同。于是,当进入死胡同时,利用栈的“回溯”可以逐个退出死胡同。
如果起点重点连通,必然能够找到从起点到终点的路径,此时,依次出栈,得到的就是从终点到起点的逆向路径。
如图所示,深红色为路径,浅红色为探测失败的死胡同。
值得注意的是,使用栈实现的迷宫路径不是最短路径。