|
利用栈和队列两种数据结构实现迷宫求解
一. 迷宫问题的描述二. 迷宫问题求解1.使用队列进行广度优先搜索C++代码实现
2. 使用栈进行深度优先搜索C++代码实现
3.代码运行结果
三.迷宫问题小实验总结
一. 迷宫问题的描述
有一张地图，0表示没有障碍物，1表示有障碍物，给你一幅地图、一个起始位置和一个目标位置，请判断是否能够从起始位置出发到达目标位置，可以的话将走过的路径用8进行标记
二. 迷宫问题求解
1.使用队列进行广度优先搜索
查找路径思路：
将起点位置存入队列中；每次访问队头元素，让队头元素出队，标记队头元素已经访问过，并在地图中将队头位置标记为8；如果队头元素就是目标位置，查找结束返回；如果不是，同时进行上下左右四个方向的移动，如果移动到的新位置是可通的并且没有被访问，将这个新位置入队；重复上一步直到队列为空，如果队列为空，说明到达不了目标位置；
C++代码实现
#include
#include
#include
using namespace std;
//位置
struct PosType
{
int _x, _y;
PosType()
:_x(0)
,_y(0)
{}
PosType(int x, int y)
:_x(x)
, _y(y)
{}
};
//判断两个位置是否相同,不能加const修饰，此处没有this指针
bool operator==(const PosType& pos1, const PosType& pos2) //const
{
return pos1._x == pos2._x && pos1._y == pos2._y;
}
//判断两个位置是否不同,不能加const修饰，此处没有this指针
bool operator!=(const PosType& pos1, const PosType& pos2) //const
{
return pos1._x != pos2._x || pos1._y != pos2._y;
}
//迷宫输入
void InitMaze(vector& map)
{
cout |