【文章內(nèi)容簡介】 i,j1 i+1,j i,j 圖 一個(gè)節(jié)點(diǎn)（ i， j）上的搜索 這樣將會(huì)出現(xiàn)如下三種情形： （ 1）若 4個(gè)候選節(jié)點(diǎn)中有 3個(gè)節(jié)點(diǎn)為不可到達(dá)節(jié)點(diǎn)，則稱該節(jié)點(diǎn)為“死點(diǎn)”（死胡同盡頭）。為防止以后再搜索該節(jié)點(diǎn)，應(yīng)將其設(shè)置為不可到達(dá)點(diǎn) ──令 maze[i][j]=2，相當(dāng)于狄修斯放了第 2條線，也相當(dāng)于將該點(diǎn)壘住。 判斷死點(diǎn)并進(jìn)行處理的算法為： if(maze[i1][j]==2 amp。amp。 maze[i][j+1]==2 amp。amp。 maze[i+1][j]==2) { maze[i][j]=2。 j。} else if(maze[i][j+1]==2 amp。amp。 maze[i+1][j]==2 amp。amp。 maze[i][j1]==2) { maze[i][j]=2。 i。 } else if(maze[i+1][j]==2 amp。amp。 maze[i][j1]==2 amp。amp。 maze[i1][j]==2) { maze[i][j]=2。 j++。 } else if(maze[i][j1]==2 amp。amp。 maze[i1][j]==2 amp。amp。 maze[i][j+1]==2) { maze[i][j]=2。 i++。 } （ 2）若該點(diǎn)不為死點(diǎn)，下一步將向一個(gè)候選節(jié)點(diǎn)搜索，稱其為已通過點(diǎn)，記以標(biāo)志：令 maze[i][j]=1，相當(dāng)于狄修斯放了一條線。同時(shí)，不管該點(diǎn)是否岔口，一律先選未通過節(jié)點(diǎn)，即先選值為 0的節(jié)點(diǎn)走，再走值為 1的點(diǎn)走， 算法為： if (maze[i1][j]==0) /* 按順時(shí)針順序先走沒有走過的點(diǎn) */ { i。 maze[i][j]=1。} else if(maze[i][j+1]==0) { j++。 maze[i][j]=1。} else if(maze[i+1][j]==0) { i++。 maze[i][j]=1。} else if(maze[i][j1]==0) { j。 maze[i][j]=1。} else if(maze[i1][j]==1) /* 按順時(shí)針順序走走過的點(diǎn) */ { maze[i][j]=2。 i。} else if(maze[i][j+1]==1) { maze[i][j]=2。 j++。} else if(maze[i+1][j]==1) { maze[i][j]=2。 i++。} else if(maze[i][j1]==1) { maze[i][j]=2。 j。} 這里沒有將原來為 1的點(diǎn)置 2，是因?yàn)椴砜谕鶗?huì)經(jīng)過多次，置 2就將其當(dāng)作直通處理了，使某些支路無法搜索。 （ 3）探索結(jié)束的條件為： i=Ei amp。amp。 j=Ej，即繼續(xù)探索的條件為： iEi || jEj。 4. 程序 include void main() { int maze[][7]={{2,2,2,2,2,2,2},{2,0,0,0,0,0,2},{2,0,2,0,2,0,2},{2,0,0,2,0,2,2}, {2,2,0,2,0,2,2},{2,0,0,0,0,0,2},{2,2,2,2,2,2,2}}。 int Si=1,Sj=1,Ei=5,Ej=5。 /* 入口與出口 */ int i=Si,j=Sj。 int count=0。 /* 記錄搜索步數(shù)變量 */ while(jEj || iEi) /* 在點(diǎn)（ i,j）上探索，不達(dá)出口時(shí)，反復(fù)進(jìn)行搜索 */ { /*****處理死點(diǎn) ******/ if (maze[i1][j]==2 amp。amp。 maze[i][j+1]==2 amp。amp。 maze[i+1][j]==2) { maze[i][j]=2。 j。} else if(maze[i][j+1]==2 amp。amp。 maze[i+1][j]==2 amp。amp。 maze[i][j1]==2) { maze[i][j]=2。 i。 } else if(maze[i+1][j]==2 amp。amp。 maze[i][j1]==2 amp。amp。 maze[i1][j]==2) { maze[i][j]=2。 j++。} else if(maze[i][j1]==2 amp。amp。 maze[i1][j]==2 amp。amp。 maze[i][j+1]==2) { maze[i][j]=2。 i++。} else maze[i][j]=1。 4. 程序（續(xù)） /***** 按順時(shí)針順序先走沒有走過的點(diǎn) *****/ if (maze[i1][j]==0) { i。 maze[i][j]=1。} else if(maze[i][j+1]==0) { j++。 maze[i][j]=1。} else if(maze[i+1][j]==0) { i++。 maze[i][j]=1。} else if(maze[i][j1]==0) { j。 maze[i][j]=1。} /***** 按順時(shí)針順序走走過的點(diǎn) *****/ else if(maze[i1][j]==1) { maze[i][j]=2。 i。} else if(maze[i][j+1]==1) { maze[i][j]=2。 j++。} else if(maze[i+1][j]==1) { maze[i][j]=2。 i++。} else if(maze[i][j1]==1) { maze[i][j]=2。 j。} count++。 /* 記錄走過點(diǎn)數(shù) */ } 4. 程序（續(xù)） /***** 打印探索結(jié)果 *****/ for(i=0。i=6。i++) { for(j=0。j=6。j++) printf(%d,maze[i][j])。 printf(\n)。 } printf(count=%d\n,count)。 /* 打印搜索步數(shù) */ } 5. 執(zhí)行結(jié)果 2,2,2,2,2,2,2 2,1,2,2,2,2,2 2,1,2,2,2,2,2 2,1,1,2,2,2,2 2,2,1,2,2,2,2 2,0,1,1,1,1,2 2,2,2,2,2,2,2 count=19 結(jié)果矩陣中的“ 1”為搜索后，找到的穿過迷宮的路線；“ 0”為未搜索過的節(jié)點(diǎn)。 三、使用堆棧組織搜索過程 1. 基于堆棧的回溯 求解本題的基本算法是回溯，而基于堆棧的回溯可以使人思路更為清晰。其基本思路如 圖 ，把對迷宮的搜索，看成一棵搜索樹的生成過程： （ 1）首先將根節(jié)點(diǎn)（入口處）壓入堆棧； （ 2） 按照下面的規(guī)則考察棧頂節(jié)點(diǎn)（圖中灰色節(jié)點(diǎn)）的可擴(kuò)展性（即前面還有路可走），直到找到一個(gè)解或得出無解（堆棧空 ——即返回到入口）的結(jié)論為止： 可擴(kuò)展，則將下一層的各個(gè)可能的節(jié)點(diǎn)按照某種順序（如順時(shí)針）壓入堆棧； 不可擴(kuò)展，則將棧頂節(jié)點(diǎn)彈出（圖中黑色的節(jié)點(diǎn)），繼續(xù)考察下一個(gè)節(jié)點(diǎn)。這下一個(gè)節(jié)點(diǎn)可能是同層的兄弟節(jié)點(diǎn)，也可能是一個(gè)上層節(jié)點(diǎn)（回溯）。 (f) 節(jié)點(diǎn) (1,5)，(1,4)都不可再擴(kuò)展，被依次彈出 ┇ (2,1) SP (1,1) (1,2) (1,3) (2,3) (2,3) (1,1) (1,3) (5,3) (e) 節(jié)點(diǎn) ()不可擴(kuò)展，被彈出 (a) 在棧中壓入根節(jié)點(diǎn) (b) 擴(kuò)展節(jié)點(diǎn)(1,1)， 壓入兩個(gè)節(jié)點(diǎn) (c) 擴(kuò)展節(jié)點(diǎn)((2,1)， 壓入一個(gè)節(jié)點(diǎn) (d) 擴(kuò)展節(jié)點(diǎn)(5,2)，壓入節(jié)點(diǎn) (5,3)(5,1) ┇ (1,2) SP (1,1) (2,1) (1,1) ┇ SP ┇ (1,2) SP (1,1) (2,1) (3,1) (1,2) (5,3) SP (1,1) (2,1) (3,1) (3,2) (4,2) (5,3) ┇ (1,2) SP (1,1) (2,1) (5,1) (3,1) (3,2) (4,2) (5,2) … (1,1) (1,1) (2,1) (1,2) (1,1) (2,1) (3,1) (1,1) (4,2) (5,2) … (1,1) (4,2) (5,2) (1,5) (2,5) (1,4) 圖 基于堆棧的回溯算法與克里特算法相比 （ 1）往棧中壓入一個(gè)節(jié)點(diǎn)，就說明該節(jié)點(diǎn)可達(dá)，相當(dāng)于鋪了第 1條線。為了避免以后對該點(diǎn)重復(fù)壓入，應(yīng)在壓入的同時(shí)，將該節(jié)點(diǎn)的置 1，即只壓入節(jié)點(diǎn)值為 0的節(jié)點(diǎn)。 （ 2）將棧頂節(jié)點(diǎn)彈出，說明該節(jié)點(diǎn)是死節(jié)點(diǎn)，相當(dāng)于鋪了第 2條線。為了將來能在迷宮矩陣中表明該點(diǎn)已經(jīng)被探索過，將其置一個(gè)特殊的數(shù) 3。 2. 定義數(shù)據(jù)結(jié)構(gòu) 基于棧的迷宮探索，需要建立兩種基本的數(shù)據(jù)結(jié)構(gòu)： 表示迷宮的數(shù)據(jù)結(jié)構(gòu) ——這在前面已經(jīng)介紹過了，就是用矩陣（二維數(shù)組）表示。 用于回溯控制的數(shù)據(jù)結(jié)構(gòu) ——堆棧。 這里首先考慮如何建立基于數(shù)組的堆棧。 （ 1）模擬迷宮的數(shù)據(jù)結(jié)構(gòu) int maze[][7]={{2,2,2,2,2,2,2}, {2,0,0,0,0,0,2}, {2,0,2,0,2,0,2}, {2,0,0,2,0,2,2}, {2,2,0,2,0,2,2}, {2,0,0,0,0,0,2}, {2,2,2,2,2,2,2}}。 int Si=1,Sj=1,Ei=5,Ej=5。 /* 入口與出口 */ （ 2）迷宮中某個(gè)節(jié)點(diǎn)的表示和探索棧 /*在 */ define N 100 typedef struct Node { int x,y。 /* 節(jié)點(diǎn)位置 */ int nodeState。 /* 節(jié)點(diǎn)狀態(tài) */ }MAZE_NODE。 typedef struct ExploreStack { MAZE_NODE explStack[N]。 /*數(shù)組棧 */ }EXP_STACK。 3. 算法設(shè)計(jì)初步 （ 1）擴(kuò)展棧頂節(jié)點(diǎn)的算法 void mazeExpand(EXP_STACK *s ) { 獲取棧頂節(jié)點(diǎn)在迷宮中的坐標(biāo) x,y。 if(探索?？?) { printf(“此迷宮找不到出口，探索過程如下： )； return。 } else if(棧頂節(jié)點(diǎn)位于出口 ) { printf(“探察結(jié)束，探察過程如下：“ )； return。 } else { if(死點(diǎn) )