迷宫问题算是dfs、bfs的经典问题了。给定一个的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动。通道我们用0表示,墙壁用1表示。5表示起点,8表示终点。求解迷宫问题思路很重要。我们可以从起点直接dfs,不通直接回溯,直到遍历到终点为止;也可以bfs,将所有能走的路全部入列,不通则队首出队,继续遍历。迷宫我们保存为mp.txt文件,放到.cpp文件同目录下,文章最后附上测试样例。
bfs,迷宫结点的存储我们使用结构体,主要是为了存储结点的前置结点来打印最短路径。从起点开始入队,能走的都加入队列;走不了就队首出队,继续将能走的都加入队列,直至找到终点。最后结果采用一个栈进行处理。
int backx = ex, backy = ey;
int step = 0;
stack<node> pqq;