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

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

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

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