一扫步、目的
1、進一步理解和掌握各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)匈子、存儲結(jié)構(gòu)和操作實現(xiàn)算法河胎。
2、掌握分析問題虎敦，求解問題的方法并提高設計編程實現(xiàn)的能力游岳。
3、熟練掌握C語言或者C++語言的各種操作其徙，制定清晰的程序流程圖和數(shù)據(jù)結(jié)構(gòu)的詳細定義胚迫。
二、實驗具體內(nèi)容
1唾那、用回溯法求解迷宮問題晌区，可以用一個棧保存探索的位置。并且在該迷宮的行走中朗若，站在一點可以有四個方向選擇，依次判斷四個方向是否能走哭懈。
2、定義一個固定格式（10*10）迷宮如下：
```
{?? 0,1,1,1,0,0,0,0,0,0,
0,0,0,1,0,0,0,1,0,0,?
0,1,0,1,1,0,0,1,0,0,?
0,1,0,0,1,0,1,1,0,0,?
0,1,0,0,1,0,1,1,0,0,?
1,1,1,0,1,0,1,0,0,0,?
0,0,1,0,0,0,1,0,1,1,?
0,0,1,0,0,0,1,0,1,1,?
0,1,1,0,1,0,1,0,0,0,?
0,0,0,0,1,0,1,1,0,0,? };
```
3遣总、并設置左上角（0，0）為入口轨功，右下角（9旭斥，9）為出口古涧，0表示通路垂券，1表示有墻羡滑。
4菇爪、用二維數(shù)組MAZE[x][y] 來表示迷宮的狀態(tài)算芯，0表示通路，1表示有墻凳宙，2表示已經(jīng)走過熙揍。
5届囚、用STL的棧儲存走過的路徑是尖，壓棧表示進入下一步，退棧表示返回上一步析砸。每個棧元素是當前位置坐標被結(jié)構(gòu)體對象包裝產(chǎn)生的爆袍。
三、分析
首先要考慮如何判斷行進方向陨囊，并且確定下一個方向可以走，再考慮如何判定走過的路胁塞，這里我采用的是將其值設置為2压语，然后每走一步就將這個位置包裝起來壓棧，假如無法再繼續(xù)行走的話就進行回溯扰才，相當于原路返回，伴隨的還有之前壓入的錯誤路徑的棧元素要出棧衩匣，反復進行從而將所有正確位置壓入棧中粥航，由棧底往棧頂遍歷，從而輸出正確路徑递雀。
四、代碼
結(jié)構(gòu)體定義：
```
struct pos{?
??? int i,j;?
};?
```
方向判定：
判斷是否有通路缀程，有則返回通路位置拦焚，無則返回原來位置?
//向上??
??? if(判定是否是通路且是否在迷宮范圍之內(nèi)且是否已經(jīng)走過了){?
????????? 執(zhí)行位置變動和將此位置標記為已走，返回下個位置?
??? }//向右
else if(判定是否是通路且是否在迷宮范圍之內(nèi)且是否已經(jīng)走過了){?
??????????????? 執(zhí)行位置變動和將此位置標記為已走赎败，返回下個位置
??? }//向下
else if(判定是否是通路且是否在迷宮范圍之內(nèi)且是否已經(jīng)走過了){?
??????????????? 執(zhí)行位置變動和將此位置標記為已走，返回下個位置
??? }//向左
else if(判定是否是通路且是否在迷宮范圍之內(nèi)且是否已經(jīng)走過了){?
??????????????? 執(zhí)行位置變動和將此位置標記為已走僵刮，返回下個位置?
??? }?
??? 否則返回上一個位置。
數(shù)據(jù)結(jié)構(gòu)操作：
stack Path;?
??? 聲明兩個結(jié)構(gòu)體對象curr勇吊，nex窍仰；?
??? 將接收入棧元素的結(jié)構(gòu)體對象curr初始化為入口元素，i=0驹吮，j=0；
??? 將入口元素入棧碟狞；
將入口（0，0）設置成走過的位置；
```
?while(判斷棧是否為空){
??????? curr=棧頂;?
??????? nex=curr;?
???????nex=Move(curr);//將curr傳入Move函數(shù)判斷方向并行走脆淹，從而發(fā)現(xiàn)通路返回下個位置或者沒有發(fā)現(xiàn)通路返回上個位置?
???????if(!(curr.i==nex.i&&curr.j==nex.j))?
??????????? 發(fā)現(xiàn)通路，將nex壓入棧頂窟绷；
??????? else?
??????????? 未發(fā)現(xiàn)通路咐柜，將棧頂出棧；
????? ??if(判斷nex是否到達出口（9拙友，9）){?
??????????? struct posroute[Path.size()];?
??????????? intz=0;?
??????????? while(判斷棧時候為空，不空執(zhí)行下列程序辐棒，空則跳出){?
??????????????? curr=棧頂元素；
??????????????? 將棧頂元素放入route結(jié)構(gòu)體類型數(shù)組中漾根；
??????????????? 棧頂出棧，以便下次操作逼蒙；
??????????? }?
??????????? for(intk=z-1;k>=0;k--){?
??????????????? 按規(guī)格輸出路徑寄疏；
??????????? }?
??????????? return;?
??????? }?
??? }?
???cout<<"NO Path!"<
```
主函數(shù)：自行想象.......
五、運行結(jié)果
迷宮如下：
0 1 1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0
0 1 0 1 1 0 0 1 0 0
0 1 0 0 1 0 1 1 0 0
0 1 0 0 1 0 1 1 0 0
1 1 1 0 1 0 1 0 0 0
0 0 1 0 0 0 1 0 1 1
0 0 1 0 0 0 1 0 1 1
0 1 1 0 1 0 1 0 0 0
0 0 0 0 1 0 1 1 0 0
則路徑為：
(0,0)->(1,0)->(1,1)->(1,2)->(2,2)
->(3,2)->(3,3)->(4,3)->(5,3)->(6,3)
->(6,4)->(6,5)->(5,5)->(4,5)->(3,5)
->(2,5)->(1,5)->(0,5)->(0,6)->(0,7)
->(0,8)->(0,9)->(1,9)->(2,9)->(3,9)
->(4,9)->(5,9)->(5,8)->(5,7)->(6,7)
->(7,7)->(8,7)->(8,8)->(8,9)->(9,9)
