使用棧和隊列實現迷宮路徑查找算法
0 綜述
最近，接到老板的一個小任務，即實現個迷宮路徑查找小程序，要求使用棧和隊列去實現。不敢怠慢，我趕緊打開Visual Studio 2012，同時在稿紙上筆畫著。題目如下：使用棧及隊列分別設計一個算法進行迷宮路徑查找（用下列二維數組表示迷宮，1表示不可通過，0表示可以通過，左上角2為起點，右下角3為終點）。
1. 棧實現
迷宮路徑查找的關鍵點在於對分支點的處理，使用棧來存儲分支點坐標的實現方法稱之為深度搜索算法。對於初始矩陣，從初始點2開始搜索四個方向上的路徑並分別對路徑進行合理標記，然後在路徑查找時可根據標記來輸出查找到的路徑。所以在查找過程中正確的標記方案將決定路徑查找的效率及可行性。對於棧來說，可以采用如下標記策略：
按照題目中的值，2為起始點，3為終點，則令flag=4即下一個合理的路徑節點權值從4開始。
規則一：對於當前節點，只有唯一路徑出口的，將出口節點權值標記為當前節點權值，如圖中4（起始點權值為4），5,7的點。
規則二：將分支點壓入棧，每次出棧的點在原有權值基礎上加1，如4節點有三個出口被壓入棧，5為第一個出棧的，6為第二個出棧的。
按照如上規則標記權值，搜索路徑時可根據從起點按照上下左右四個路徑查找權值最大的點作為路徑下一個節點，即可找查找到最終路徑（2-4-6-7-3）。
2. 隊列實現
使用隊列來存儲分支點坐標的實現方法稱之為廣度搜索算法。和上述棧的查找方法不同之處在於，標記策略的不同。對於隊列來說，可以采用如下標記策略：
按照題目中的值，2為起始點，3為終點，和上述棧一致，從4開始標記路徑。
規則一：對於同一級別的廣度搜索節點采用統一的權值。
規則二：記錄同一級別點的個數，當進入下一級別隊列時，權值加1。
按照如上規則標記權值，搜索路徑時可采用逆向搜索方法即從終點前搜索最小值作為路徑有效節點（3-9-8-7-6-5-4-2）。
3. 實現代碼與結果演示
/* =========================================================
* 迷宮路徑搜索算法
* =========================================================
* 20141203
*/
#include
#include
#include
#include
#include
using std::cout;
using std::endl;
using std::stack;
using std::queue;
#define N 15
typedef struct{
int x;
int y;
}PointPos;
int map[15][15] = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
/* =========================================================
* 函數聲明
* =========================================================
*/
// 搜尋起始點和終點坐標函數
void FindMarkedPos(PointPos& start,PointPos& end);
// 恢復map初始數據函數
void InitMap();
// 基於Stack的深度優先搜索算法
void UseStack(PointPos start,PointPos end);
// 基於Queue的廣度優先搜索算法
void UseQueue(PointPos start,PointPos end);
// Stack結果輸出函數
void StackOutPut(PointPos start);
// Queue結果輸出函數
void QueueOutPut(PointPos start);
/* =========================================================
* 主函數
* =========================================================
*/
void main(void)
{
// 其實結束標記點定義
PointPos start,end;
// 尋找標記點函數
FindMarkedPos(start,end);
// Stack深度優先搜索函數
UseStack(start,end);
// 輸出 Stack深度優先搜索的結果
cout<<"Stack - Search Result:"< pointstack;
for(int i=0; i<15; i++)
{
for(int j=0; j<15; j++)
{
if(2 == map[i][j])
{
start.x = i;
start.y = j;
flag = flag + 1;
}
else if(map[i][j] == 3)
{
end.x = i;
end.y = j;
flag = flag + 1;
}
if(2 == flag) break;
}
if(2 == flag) break;
}
}
/* =========================================================
* 基於Stack的深度優先搜索算法
* =========================================================
*/
void UseStack(PointPos start,PointPos end)
{
// 定義存儲棧
stack pointstack;
// 標記路徑權值，定義點坐標和臨時變量
int flag = 4;
PointPos pointpos,pointtemp;
// 將起點坐標入棧，並進入循環搜索
pointstack.push(start);
while(!pointstack.empty())
{
pointpos = pointstack.top();
pointstack.pop();
// count記錄每個坐標點有路徑的方向個數
int i,j,count=0;
i = pointpos.x;
j = pointpos.y;
//cout<0 && i0 && j 3)
map[i][j] = 0;
}
}
/* =========================================================
* 基於Queue的廣度優先搜索算法
* =========================================================
*/
void UseQueue(PointPos start,PointPos end)
{
// 定義存儲隊列
// 分支點的權值為等同，即隊列同等級同權值
// 采用逆向搜索路徑的算法，這樣分支點可實現唯一路徑查找
queue pointqueue;
queue countqueue;
// 標記路徑權值，定義點坐標和臨時變量
// Count為一次廣度的同級別點個數
int flag = 3,Count=1,count=0;
PointPos pointpos,pointtemp;
// 將起點坐標入隊列，並進入循環搜索
pointqueue.push(start);
while(!pointqueue.empty())
{
pointpos = pointqueue.front();
pointqueue.pop();
if(Count<1 && !countqueue.empty())
{
Count = countqueue.front();
countqueue.pop();
}
if(0 == Count) continue;
--Count;
// count記錄每個坐標點有路徑的方向個數
int i,j;
i = pointpos.x;
j = pointpos.y;
//cout<0 && i0 && j0 && i max)
{
ni = i-1;
nj = j;
max = map[i-1][j];
}
if(3 == map[i-1][j])
break;
if(map[i+1][j] > max)
{
ni = i+1;
nj = j;
max = map[i+1][j];
}
if(3 == map[i+1][j])
break;
}
// 左右判斷
if(j>0 && j max)
{
ni = i;
nj = j-1;
max = map[i][j-1];
}
if(3 == map[i][j-1])
break;
if(map[i][j+1] > max)
{
ni = i;
nj = j+1;
max = map[i][j+1];
}
if(3 == map[i][j+1])
break;
}
//cout< 3)
cout<<0<<' ';
else
cout<0 && i w)
{
ni = i-1;
w = map[i-1][j];
}
if(map[i+1][j] > w)
{
ni = i+1;
w = map[i+1][j];
}
}
if(j>0 && j w)
{
nj = j-1;
w = map[i][j-1];
}
if(map[i][j+1] > w)
{
nj = j+1;
w = map[i][j+1];
}
}
i = ni;
j = nj;
while(2 != map[i][j])
{
// 上下判斷
if(i>0 && i0 && j 3)
cout<<0<<' ';
else
cout<
