本文適合于對迷宮問題已有初步研究,或閱讀代碼能力較強的人.

　　因此,如果你對迷宮問題一無所知,請參考其他更詳細的資料.

　　迷宮問題,是一個對棧(Stack)典型應(yīng)用的例子之一.

　　假如,有如下10X10的迷宮(0代表通路,1代表障礙),我們需要用寫程序來找出迷宮的出口.

1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1

那么,我們可以通過兩種方式完成.

方式一:通過利用棧FILO(First In Last Out)的特性

核心代碼

/* *函數(shù)說明:通過棧來進行迷宮求解 *參數(shù)說明: * Maze:迷宮地圖數(shù)組 * sz:迷宮大小 * entry:迷宮入口點 * path:用于尋找迷宮出口的棧 *返回值:找到出口返回true,沒找到返回false. */ bool FindMazePath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path){//將入口壓棧path.push(entry);//如果棧不為空while(!path.empty()){//獲取棧頂元素,即上一次走的路徑Pos cur = path.top();//將其標記為已走過Maze[cur.x*sz+cur.y] = 3;//找到出口if(sz-1==cur.x){return true;}Pos next = cur;//下一步,向右移動next.x += 1;if(CheckIsAccess(Maze,sz,next)){//可以向右移動,將當前步入棧path.push(next);continue;}next = cur;//下一步,向左移動next.x -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向左移動,入棧path.push(next);continue;}//下一步,向上移動next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){//可以向上移動path.push(next);continue;}next = cur;//向下移動next.y -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向下移動path.push(next);continue;}//上、下、左、右都不能走path.pop();}return false; }

方式二:通過遞歸

核心代碼

/* *函數(shù)說明:根據(jù)遞歸尋找迷宮出口 *參數(shù)說明 * Maze:迷宮地圖 * sz:迷宮大小 * entry:迷宮入口 * path:用來判斷是否存在出口的棧 *返回值:無(如果存在出口,棧為空;如果不存在出口,棧中存在起點坐標) */ void FindMazePathR(int *Maze,size_t sz,Pos &entry,stack<Pos> & path){//將入口壓棧path.push(entry);Pos cur = entry;//將已走過的路標記為3Maze[cur.x*sz+cur.y] = 3;//找到出口,直接返回if(sz-1==entry.x){//將起點坐標彈出path.pop();return ;}Pos next = cur;//右next.x += 1;if(CheckIsAccess(Maze,sz,next)){//以當前位置為起點,遞歸進行下一步FindMazePathR(Maze,sz,next,path);}next = cur;//左next.x -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//上next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//下next = cur;next.y -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}path.pop(); }

最后,附上整個程序的完整代碼(代碼量較少,聲明與實現(xiàn)我就不分文件了)

迷宮問題求解完整代碼

//相關(guān)函數(shù)的聲明與實現(xiàn) #ifndef __MAZE_H__ #define __MAZE_H__ #include<iostream> #include<iomanip> #include<stack> #include<assert.h> namespace Maze{using namespace std;//迷宮大小static const int N = 10;//迷宮地圖文件名static const char *const FILENAME = "MazeMap.txt";//坐標struct Pos{int x; //橫坐標(本質(zhì)是數(shù)組arr[i][j]的j)int y; //縱坐標(本質(zhì)是數(shù)組arr[i][j]的i)};/*函數(shù)說明:從文件中獲取迷宮地圖參數(shù)說明:Maze:迷宮地圖數(shù)組sz:迷宮大小返回值:無*/void GetMaze(int *Maze,size_t sz){FILE *fp = fopen(FILENAME,"r");//打開失敗if(NULL==fp){//輸出錯誤信息perror(FILENAME);//結(jié)束程序exit(1);}//將文件中的迷宮地圖讀入Maze數(shù)組內(nèi)for(size_t i=0; i<sz; ++i){for(size_t j=0; j<sz;){//從文件流中獲取字符char tmp = getc(fp);//字符為0或為1時,導入數(shù)組if(tmp=='0'||tmp=='1'){Maze[i*sz+j]=tmp -'0';++j;}else if(EOF==tmp){//文件已讀完,循環(huán)還未停止//說明此處文件中的迷宮地圖存在問題assert(false);return ;}}}//關(guān)閉文件fclose(fp);}/*函數(shù)說明:打印迷宮參數(shù)說明:Maze:迷宮地圖數(shù)組sz:迷宮大小返回值:無*/void PrintMaze(int *Maze,size_t sz){cout<<setw(2);for(size_t i=0; i<sz; ++i){for(size_t j=0; j<sz; ++j){cout<<Maze[i*sz+j]<<setw(2);}cout<<endl;}}/*函數(shù)說明:檢測當前位置是否可以通過參數(shù)說明:Maze:迷宮地圖數(shù)組sz:迷宮大小cur:當前所在位置返回值:可以通過返回true,不能通過返回false.*/bool CheckIsAccess(int *Maze,size_t sz,Pos cur){if(cur.x>=0 && cur.x<sz && //行坐標是否越界cur.y>=0 && cur.y<sz && //列坐標是否越界Maze[cur.x*sz+cur.y]==0 ){ //所在行列是否可以通過return true;}return false;}/*函數(shù)說明:通過棧來進行迷宮求解參數(shù)說明:Maze:迷宮地圖數(shù)組sz:迷宮大小entry:迷宮入口點path:用于尋找迷宮出口的棧返回值:找到出口返回true,沒找到返回false.*/bool FindMazePath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path){//將入口壓棧path.push(entry);//如果棧不為空while(!path.empty()){//獲取棧頂元素,即上一次走的路徑Pos cur = path.top();//將其標記為已走過Maze[cur.x*sz+cur.y] = 3;//找到出口if(sz-1==cur.x){return true;}Pos next = cur;//下一步,向右移動next.x += 1;if(CheckIsAccess(Maze,sz,next)){//可以向右移動,將當前步入棧path.push(next);continue;}next = cur;//下一步,向左移動next.x -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向左移動,入棧path.push(next);continue;}//下一步,向上移動next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){//可以向上移動path.push(next);continue;}next = cur;//向下移動next.y -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向下移動path.push(next);continue;}//上、下、左、右都不能走path.pop();}return false;}/**函數(shù)說明:根據(jù)遞歸尋找迷宮出口*參數(shù)說明* Maze:迷宮地圖* sz:迷宮大小* entry:迷宮入口* path:用來判斷是否存在出口的棧*返回值:無(如果存在出口,棧為空;如果不存在出口,棧中存在起點坐標)*/void FindMazePathR(int *Maze,size_t sz,Pos &entry,stack<Pos> & path){//將入口壓棧path.push(entry);Pos cur = entry;//將已走過的路標記為3Maze[cur.x*sz+cur.y] = 3;//找到出口,直接返回if(sz-1==entry.x){//將起點坐標彈出path.pop();return ;}Pos next = cur;//右next.x += 1;if(CheckIsAccess(Maze,sz,next)){//以當前位置為起點,遞歸進行下一步FindMazePathR(Maze,sz,next,path);}next = cur;//左next.x -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//上next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//下next = cur;next.y -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}path.pop();} } #endif

迷宮求解測試代碼

#include"Maze.h" using namespace Maze; void MazeTest(){int arr[N][N]; //迷宮地圖Pos entry = {2,0}; //起點坐標stack<Pos> path; //棧GetMaze((int *)arr,N); //將文件中迷宮導入到arr數(shù)組中PrintMaze((int *)arr,N);//打印迷宮FindMazePath((int *)arr,N,entry,path);//找迷宮出口cout<<endl<<endl; //換行處理(使界面更整齊)PrintMaze((int *)arr,N);//打印走過的迷宮 } int main(){MazeTest();return 0; }

總結(jié):

　　1.利用棧去尋找迷宮出口,棧內(nèi)最終會保存從入口到出口的所有路徑.

　　2.利用遞歸去尋找迷宮出口,傳進去的棧僅僅只是用來判斷迷宮是否有出口,

　　3.利用遞歸去尋找出口時,因為遞歸的特性,將會遍歷完迷宮內(nèi)的所有路徑.

　　最后,還有一個問題:如果一個迷宮存在多條路徑可以到達出口,那么如何得到迷宮到出口的最短路徑？？？

　　有機會的話,我將會在下篇文章討論此事.

　　附上工程文件:http://pan.baidu.com/s/1gfoNrLD

轉(zhuǎn)載于:https://www.cnblogs.com/shujujiegou/p/6128661.html

總結(jié)

以上是生活随笔為你收集整理的数据结构之迷宫问题求解(一)利用栈与递归求解出口的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。