迷宮問題是一道經(jīng)典的回溯算法問題，給定一個迷宮矩陣，矩陣中的1表示障礙，0表示可走通路，給定迷宮入口出口，要求尋找從入口穿過迷宮到達出口的所有路徑，有則輸出，無則給出提示。一本合格的數(shù)據(jù)結構教科書一般都會介紹迷宮問題，網(wǎng)上的分析也是鋪天蓋地，這里就不再贅述重復的內容了。廢話不多說，簡單介紹一下程序，然后上代碼。

該程序用二維數(shù)組表示迷宮，用另一個二維數(shù)組記錄迷宮中的位置是否已經(jīng)走過，同時用一個鏈式棧存放搜索出的臨時路徑。程序從迷宮入口開始試探，隨著回溯試探過程的進行，鏈式棧的長度不斷變化，當試探到迷宮出口時，鏈表中存放的就是一條完整的穿過迷宮的路徑了，輸出路徑后回溯，繼續(xù)試探下一條路徑，當回溯到入口時沒有新的可走方向時整個回溯試探的過程也就結束了。鏈表節(jié)點中除了存放被路徑連接的各單元的行列標外，還存放有由該節(jié)點代表的單元前往該節(jié)點的后繼節(jié)點代表的單元的方向，這么做是為了方便回溯操作的進行。

為方便起見，程序中迷宮的入口是固定的，為左上角單元，出口同樣固定，為右下角單元。這并不妨礙程序的普適性，只要稍加修改就可以使程序適用于任意給定的出口和入口的情形。

啰嗦了這么半天，下面該上代碼了，代碼用C語言編寫，具體如下。