利用棧實作迷宮的求解

　　問題描述：這時實驗心理學中的一個典型的問題，心理學家吧一隻老鼠從一個無頂的大盒子的入口處趕進迷宮。迷宮設定很多隔壁，對前進方向形成了許多障礙，心理學家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠仔迷宮中尋找通路以到達出口。

　　求解思想：回溯法是一種不斷試探且及時糾正錯誤的搜尋方法，下面的求解過程采用回溯法。從入口出發，按某一方向向前探索，若能走通（未走過

的），即某處可以到達，則到達一個新點，否則試探下一個方向；若所有的方向均沒有通路，則沿原路傳回前一點，換下一個方向繼續試探，直到所有可能的通路都

搜尋到，或找到一條通路，或無路可走又傳回到入口點。這裡可以用一個棧來實作，每走一步，将該位置壓入棧中，若該點無路可走，則出棧傳回上一位置。

　　需要解決的四個問題：

　　（1）表示迷宮的資料結構

　　設迷宮為m行n列，利用數組maze[m][n]來表示一個迷宮，maze[i][j]=0或1，其中0表示通路，1表示不通。迷宮該數組四邊都為1，代表迷宮四周都是牆。這樣就可以保證每個點都有8個方向可以試探。

　　入口為（1,1），出口為（6,8）

　　（2）試探方向

　　迷宮中間每個點都有8個方向可以試探。其增量數組可以用一個1*2的二維數組move表述，具體值如下：

　　在move數組中，x表示橫坐标的增量，y表示縱坐标的增量。

　　（3）棧中存放元素的設計

　　棧中所存放的元素應該包含所到達的每點的坐标以及從該點沿哪個方向向下走的。可以用一個類表示：

　（4）防止重複到達某點而發生死循環

　　可以用兩種方法來實作，第一種就是另外設定一個标志數組mark[m][n],它的所有元素初始都為0，一旦到達某點，則設定該點的标志位1，

下次試探的時候就不再走這點了。第二種就是當到達某點的時候，使maze[i][j]置為-1，以便差別為達到的點，同樣也可以防止走重複點的作用。

具體代碼如下：

輸出結果如下：

6:8

5:8

5:7

5:6

4:5

3:5

3:4

3:3

2:2

　　由于棧是後進先出的，是以結果應該從下面看起（2,2）->（3,3）->（3,4）->（3,5）->（4,5）->（5,6）->（5,7）->（5,8）->（6,8）

有運作結果可以看出來，棧中所存儲的就是迷宮的一條通路。

　　上面那個代碼有一點點小問題，非常感謝問題的提出者，修改如下：