栈和队列实现迷宫路径搜索

• 题目
• 栈实现
• • 思想
  • 代码实现
• 队列实现
• • 思想
  • 代码实现
• 完整代码

自定义一个迷宫，行、列值>8，它有一个出口和一个入口，先输出迷宫图形，然后找出一条从入口到出口的路径
基本接口：

class MazeWay {
public:
	// 定义迷宫
	vector> mazeSet = { {1,1,1,1,1,1,1,1,1,1,1},{1,1,0,0,0,0,0,0,0,0,1},
									{1,1,0,0,1,1,1,1,1,0,1},{1,1,1,0,0,0,1,0,1,0,1},
									{1,1,1,1,0,1,0,1,1,1,1},{1,0,1,0,0,0,0,0,0,0,1},
									{1,0,1,0,1,1,1,1,1,0,1},{1,0,0,0,1,0,0,0,1,0,1},
									{1,1,1,1,1,0,1,0,1,0,1},{1,0,0,0,1,0,1,0,1,0,1},
									{1,0,1,0,0,0,1,0,0,0,1},{1,1,1,1,1,1,1,1,1,1,1}};
	//vector> mazeSet = { {1,1,1,1,1,1,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0,0,0,0,0,1},
	//								  {1,0,0,0,0,0,1,1,1,1,1,0,1},{1,1,1,1,1,0,1,0,0,0,0,0,1},
	//								  {1,0,0,0,1,0,1,0,0,0,0,0,1},{1,0,0,0,1,0,1,0,0,0,0,0,1},
	//								  {1,0,0,0,1,0,1,0,0,0,0,0,1},{1,0,1,1,1,0,1,0,0,0,0,0,1},
	//								  {1,0,0,0,0,0,1,0,0,0,0,0,1},{1,0,0,0,1,0,1,1,1,1,1,0,1},
	//								  {1,0,0,0,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1,1,1,1} };
	//pair beginN{ 5,3 },endN{3,7};
	pair beginN{ 3,9 }, endN{ 10,1 };										// 定义终点和起始点
	void showMaze(vector> mazeGet);										// 迷宫可视化
	int findWay(vector> mazeMap, pair &place);				// 查找路线
	stack> mazePathStack(vector> mazeGet);				// 主函数（栈实现）
	vector> mazePathQueue(vector> mazeGet);				// 主函数（队列实现）
};

通过回溯法进行路径搜索，先朝一个指定的方向进行不断的前行，如果没有找到路，不断沿走过的路回退，找到没有走过的路，寻找新的路去走。
额，可能表述的不是很清楚，具体可以Baidu一下回溯法，有很多大神讲的不错。

int MazeWay::findWay(vector> mazeMap, pair& place)
{
	// 上
	if (mazeMap[place.first - 1][place.second] == 0) {
		place.first--;
		return 1;
	}
	// 右
	else if (mazeMap[place.first][place.second + 1] == 0) {
		place.second++;
		return 1;
	}
	// 下
	else if (mazeMap[place.first + 1][place.second] == 0) {
		place.first++;
		return 1;
	}
	// 左
	else if (mazeMap[place.first][place.second - 1] == 0) {
		place.second--;
		return 1;
	}
	return 0;
}
// 栈实现迷宫路径查找
stack> MazeWay::mazePathStack(vector> mazeGet)
{
	stack> waySign;
	waySign.push(beginN);
	pair NodeSin;
	while (!waySign.empty()) {
		NodeSin = waySign.top();
		if (NodeSin == endN)return waySign;			// 找到终点，出口
		mazeGet[NodeSin.first][NodeSin.second]--;	// 走过的路做标记
		findWay(mazeGet, NodeSin);					// 找没有走过的路
		if (NodeSin != waySign.top()) {				// 如果找到了路
			waySign.push(NodeSin);					// 插入新路
		}
		else waySign.pop();							// 没有找到路，退回重新找路
	}
	return stack>();					// 没有找到路，返回空
}

通过广度优先的方式进行路径搜索，将所有可以走的路进行搜索，将现在所有可能走的路存储到队列，然后再不断提取和存储新的可能路线。
如果还是觉得不太理解的话，也还是百度吧（泪奔）

vector> MazeWay::mazePathQueue(vector> mazeGet)
{
	queue>> waySearch;
	vector> waySave = { beginN };
	waySearch.push(waySave);
	while (!waySearch.empty())
	{
		waySave = waySearch.front();
		waySearch.pop();
		for (int i = -1; i < 2; i ++) {
			for (int j = -1; j < 2; j++)
			{
				if (i && j)continue;
				auto waySet = waySave;
				pair node = { waySet.back().first + i ,waySet.back().second + j };
				if (node.first == endN.first && node.second == endN.second) {
					waySet.push_back(node);
					return waySet;
				}
				if (!mazeGet[node.first][node.second]) {
					mazeGet[node.first][node.second] = 1;
					waySet.push_back(node);
					waySearch.push(waySet);
				}
			}
		}
	}
	return vector>();
}

#include
#include
#include