迷宮問題的三種解法

堆疊解決—深度優先遍歷思想

#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;
}