棧是數據結構中一種重要的線性結構，限定僅在表尾進行插入和刪除操作的線性表，因此我們也可以認為它是一種特殊的線性表。由于棧的這個特點，我們又可以稱其為后進先出的結構。如圖所示：

? ? ? ?由于棧具有后進先出的性質我們可以利用，是程序設計中一個有用的工具。利用棧我們可以來實現數制轉換、后綴表達式求值、迷宮求解等等。在書本上我們可以看到用C語言實現的簡單思路，但是程序仍舊存在許多bug。今天，我想嘗試用強大的C++來實現。

? ? ? 迷宮問題的求解思路大致則是從入口出發，順著某一方向向前探索，若能走通，則繼續向前探索；若不能走通，則換一方向進行探索，直至所有可能的通路都探索完為止。利用棧的特性，我們可以將探索過可通的路依次進棧，如果遇到不通的路則進行出棧操作，進行回退，重復探索。

? ? ? ?ps：為了方便起見我利用了一個記事本來存放迷宮，用1表示不通，0表示通路。將走過的路程標注為2.

代碼實現：

struct?Pos ?//可通過下標訪問位置 {int?_ROW;int?_COL; };void?GetMaze(int?*a,int?n) //從文件中讀出迷宮地圖 {FILE*?fout=fopen("Maze.txt","r");assert(fout);for(int?i=0;?i<n;?i++){for(int?j=0;?j<n;?){char?ch=fgetc(fout);if(ch=='0'?||?ch=='1'){a[i*n+j]=ch-'0';++j;}else{continue;}}}fclose(fout); }bool?CheckIsAccess(int?*a,int?n,Pos?next)//檢查是否為通路 {assert(a);if(?(next._ROW>=0)?&&?(next._ROW<n)?&&?(next._COL>=0)?&&?(next._COL<n)?&&?(a[next._ROW*n+next._COL]==0)){return?true;}else{return?false;} }bool?MazePath(int?*a,int?n,Pos&?entry,stack<Pos>&?path) ???//探索過程 {Pos?cur=entry;path.push(cur);while(!path.empty()){Pos?next=cur;a[cur._ROW*n+cur._COL]=2;if(next._ROW==n-1)?/*||?next._ROW==0?||?next._COL==n-1?||??next._COL==0*/{return?true;}//判斷上下左右是否為通路?next=cur;next._ROW--;//?上if(CheckIsAccess(a,n,next)){ cur=next;path.push(cur);continue;}next=cur;next._ROW++;//下if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}next=cur;next._COL--;//左if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}next=cur;next._COL++;//右if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//回退cur=path.top();path.pop();} ??? }void?PrintMaze(int?*a,int?n)???//輸出迷宮 {for(int?i=0;?i<n;?i++){for(int?j=0;?j<n;?j++){cout<<a[i*n+j]<<"?";}cout<<endl;} }

轉載于:https://blog.51cto.com/luminous/1762736

總結

以上是生活随笔為你收集整理的应用栈求解迷宫问题（C++实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。