迷宫问题的三种解法

栈解决—深度优先遍历思想

#include<iostream>
using namespace std;
#include<stack>
#include<forward_list>
//迷宫 1为墙 0为通路
int Graph[][10] =
{
        {1,1,1,1,1,1,1,1,1,1},
		{1,0,0,1,0,0,0,1,0,1},
		{1,0,0,1,0,0,0,1,0,1},
		{1,0,0,0,0,1,1,0,0,1},
		{1,0,1,1,1,0,0,0,0,1},
		{1,0,0,0,1,0,0,0,0,1},
		{1,0,1,0,0,0,1,0,0,1},
		{1,0,1,1,1,0,1,1,0,1},
		{1,1,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1}
};
//迷宫 起点 终点
bool findPath(int (*Graph)[10],int x1,int y1,int x2,int y2)
{
	//记录迷宫路径的一维数组
	forward_list<pair<int, int>> path;
	//创建栈
	stack<pair<int, int>> s;
	//将入口加入栈中
	s.push({x1,y1});
	//设置入口点的经过标记
	Graph[x1][y1]= -1;
	//记录弹出栈顶的元素
	pair<int, int> top;
	//设置有没有找到可走的相邻的方块
	bool find = false;
	//设置方向--右 下 左 上
	int di = 0;
	//当栈不为空时
	while (!s.empty())
	{
		//弹出栈顶元素，判断是否为终点
		top=s.top();
		//如果走到迷宫终点就输出完整迷宫路径
		if (top.first == x2 && top.second == y2)
		{
			cout << "迷宫完整路径：" << endl;
			//将栈顶元素，挨个弹出放入path数组中
			while (!s.empty())
			{
				path.emplace_front(s.top());
				s.pop();
			}
			for (forward_list<pair<int, int>>::iterator it = path.begin(); it != path.end(); it++)
				cout << "{" << (*it).first << "," << (*it).second << "}" << endl;
			return true;
		}
		//如果没走到终点
	    //下面就要考虑，是不是要往四周某个方向前进，去寻找终点
		di = 0;//每一次到了一个新的点，要往它四周探测，都要将方向归0
		find = false;//还未找到新的可走方向
		int row, c;//行 列
		while (di < 4)//四个方向还没有都探测完
		{
			switch (di)//右 下 左 上
			{
			case 0:
			{
				c=top.second+1;
				row= top.first;
				break;
			}
			case 1:
			{
				row=top.first+1;
				c = top.second;
				break;
			}
			case 2:
			{
				c=top.second-1;
				row = top.first;
				break;
			}
			case 3:
			{
				row=top.first-1;
				c = top.second;
				break;
			}
			}
			if (Graph[row][c] == 0)//表示有通路
			{
				s.push({ row,c });
				Graph[row][c] = -1;
				find = true;
				break;
			}
			//没有通路，就再探测其他方向
			di++;
		}
		//如果四个方向探测完，方向四个方向都无法通过，就要弹出栈顶元素，进行回退操作
		if (find == false&&di==4)
		{
			s.pop();
		}
	}
	return false;//没找到终点
}
 
int main()
{
	findPath(Graph, 1,1,8,8);
	system("pause");
	return 0;
}

队列解决------广度优先遍历—找到最短路径

#include<iostream>
using namespace std;
#include<vector>
#include<queue>
#include<stack>
//迷宫 1为墙 0为通路
int Graph[6][6] =
{
{ 1,1,1,1,1,1},
{ 1,0,1,1,1,1},
{ 1,0,1,0,1,1},
{ 1,0,0,0,1,1},
{ 1,1,0,0,0,1},
{ 1,1,1,1,1,1},
};
struct elm
{
	pair<int, int> pos;//当前位置
	int pre;//前驱
	int cur;//当前位置
};
//迷宫 起点 终点
bool findPath(int (*Graph)[6],int x1,int y1,int x2,int y2)
{
      //记录最短路径的数组
	vector<elm> path;
	//队列
	queue<elm> q;
	//将起点加入队列
	elm e = { {x1,y1},-1,0 };//起点的前驱是-1,当前位置为0
	q.push(e);
	//设置经过的标记
	Graph[x1][y1] = -1;
	//方向
	int di = 0;
	//是否存在新的方向可以走
	bool find = false;
	//记录终点的前驱
	int endPre;
	//记录当前队列已经插入的元素个数
	int num = 0;
	//如果队列不为空
	while (!q.empty())
	{
		//对头元素放入path数组中
		path.push_back(q.front());
		//出队
		e = q.front();
		q.pop();
		//如果找到出口就结束循环
		if (find)
		{
			cout << "最短路径为：" << endl;
			vector<elm>::reverse_iterator it = path.rbegin();
			stack<elm> s;
			for (; it != path.rend(); it++)
			{
				if ((*it).cur == endPre)
				{
					s.push(*it);
					endPre = (*it).pre;
				}
			}
			while (!s.empty())
			{
				cout << "{" << s.top().pos.first << "," << s.top().pos.second << "}" << endl;
				s.pop();
			}
			cout << "{" << x2 << "," << y2 << "}" << endl;
			return true;
		}
		//将对头元素，四周能走的点全部按顺序依次加入队列
		di = 0;
		int row, c;
		while (di < 4)//右 下 左 上
		{
			switch (di)
			{
			case 0:
			{
				c = e.pos.second+1;
				row=e.pos.first;
				break;
			}
			case 1:
			{
				c = e.pos.second;
				row = e.pos.first+1;
				break;
			}
			case 2:
			{
				c = e.pos.second-1;
				row = e.pos.first;
				break;
			}
			case 3:
			{
				c = e.pos.second;
				row = e.pos.first-1;
				break;
			}
			}
			//判断当前方向是否为通路
			if (Graph[row][c] == 0)
			{
				num++;
				//获取当前要走方向的左标，判断是否可以走通
				//并且该点的前驱是刚刚出队的元素
				elm el = { {row,c},e.cur,num};
				//当前点入队
				q.push(el);
				//设置走过的标记
				Graph[row][c] = -1;
				//判断当前方向是否等于终点
				if (row == x2 && c == y2)
				{
					endPre = e.cur;
					find = true;
					break;
				}
			}
			di++;
		}
	
	}
	cout << "没找到出口" << endl;
	return false;//没找到出口
}
 
int main()
{
	findPath(Graph, 1,1,4,4);
	system("pause");
	return 0;
}

递归解决—求解全部路径

#include<iostream>
using namespace std;
#include<vector>
//迷宫 1为墙 0为通路
int Graph[][6] =
{
		 {1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 1, 1},
		{1, 0, 1, 0, 0, 1},
		{1, 0, 0, 0, 1 ,1},
		{1, 1, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1}
};
//迷宫 起点 终点
void findPath(int(*Graph)[6], int x1, int y1, int x2, int y2)
{
	int i, j;
	static vector<pair<int, int>> path;
	if (x1 == x2 && y1 == y2) 
	{
		//将终点坐标进入路径中 
		path.push_back({ x1,y1 });

		cout << "迷宫路径如下：" << endl;
		for (int i = 0; i < path.size(); i++)
		{
			cout << "{" << path[i].first << "," << path[i].second << "}" << endl;
		}
	}
	else {
		if (Graph[x1][y1] == 0) {
			int di = 0;	//用于四个方位移动的变量
			while (di < 4) {
				//第一步：将(xi,yi)进入path路径中 
				path.push_back({ x1,y1 });

				//对四个方位寻找相邻方块 
				switch (di) {
				case 0: {i = x1, j = y1+1; break; }
				case 1: {i = x1+1, j = y1; break; }
				case 2: {i = x1, j = y1-1; break; }
				case 3: {i = x1-1, j = y1; break; }
				}

				//第二步：将mg[xi][yi]=-1，避免来回走动 
				Graph[x1][y1] = -1;

				//第三步：递归调用迷宫函数求解小问题 
				findPath(Graph, i, j, x2, y2);

				//第四步：回退path数组中的元素，并将回退元素mg[xi][yi]=0来寻找其他路径 
				path.pop_back();
				Graph[x1][y1] = 0;
				di++;
			}
		}
	}
}

int main()
{
	findPath(Graph, 1, 1, 4, 4);
	system("pause");
	return 0;
}