C語(yǔ)言重解經(jīng)典回溯算法案例

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

該程序用二維數(shù)組表示迷宮，用另一個(gè)二維數(shù)組記錄迷宮中的位置是否已經(jīng)走過(guò)，同時(shí)用一個(gè)鏈?zhǔn)綏４娣潘阉鞒龅呐R時(shí)路徑。程序從迷宮入口開(kāi)始試探，隨著回溯試探過(guò)程的進(jìn)行，鏈?zhǔn)綏５拈L(zhǎng)度不斷變化，當(dāng)試探到迷宮出口時(shí)，鏈表中存放的就是一條完整的穿過(guò)迷宮的路徑了，輸出路徑后回溯，繼續(xù)試探下一條路徑，當(dāng)回溯到入口時(shí)沒(méi)有新的可走方向時(shí)整個(gè)回溯試探的過(guò)程也就結(jié)束了。鏈表節(jié)點(diǎn)中除了存放被路徑連接的各單元的行列標(biāo)外，還存放有由該節(jié)點(diǎn)代表的單元前往該節(jié)點(diǎn)的后繼節(jié)點(diǎn)代表的單元的方向，這么做是為了方便回溯操作的進(jìn)行。

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

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