求解迷宮問題(c語言,很詳細(xì)哦)

1、求迷宮問題就是求出從入口到出口的路徑。在求解時，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前試探，若能走通，則 繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)試探，直至所有可能的 通路都試探完為止。為了保證在任何位置上都能沿原路退回（稱為回溯）, 需要用一個后進(jìn)先出的棧來保存從入口到當(dāng)前位置的路徑。首先用如圖3.3所示的方塊圖表示迷宮。對于圖中的每個方塊，用空白表示通道，用陰影表示墻。所求路徑必須是簡單路徑，即在 求得的路徑上不能重復(fù)出現(xiàn)同一通道塊。出口13.3 迷宮示意圖方位1（W+1）圖方位圖為了表示迷宮,設(shè)置一個數(shù)組mg,其中每個元素表示一個方塊的狀態(tài)，為 0時表示對應(yīng)方塊是

2、通道，為1時表示對應(yīng)方塊為墻，如圖3.3所示的迷 宮，對應(yīng)的迷宮數(shù)組mg如下:int mgM+1N+1= /*M=10,N=10*/1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1 ;偽代碼:while （棧不空）若當(dāng)前位置可通，則將當(dāng)前位置插入棧

3、頂寸/納入路徑若該位置是出口位置，則算法結(jié)束；IIBI/此時棧中存放的是一條從入口位置到出位置的路徑 否則切換當(dāng)前位置的北鄰方塊為新的當(dāng)前位置；否則若棧不空且棧頂位置尚有其他方向未被探索,則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊; 若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置了/從路徑中刪去該通道塊若棧不空”則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？?c語言描述如下:void mgpath() /* 路徑為 :(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+; /* 初始方塊進(jìn)棧 */Stacktop.i=1;Stac

4、ktop.j=1;Stacktop.di=-1;mg11=-1;while (top-1)/*棧不空時循環(huán) */i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M-2 & j=N-2) /* 找到了出口 ,輸出路徑 */printf( 迷宮路徑如下 :n);for (k=0;k=top;k+)printf(t(%d,%d),Stackk.i,Stackk.j);if (k+1)%5=0)printf(n);printf(n);return;find=0;while (di4 & find=0) /* 找下一個可走方塊 */ di+;switch(d

5、i)case 0:i=Stacktop.i-1;j=Stacktop.j; break;case 1:i=Stacktop.i;j=Stacktop.j+1; break;case 2:i=Stacktop.i+1;j=Stacktop.j; break;case 3:i=Stacktop.i;j=Stacktop.j-1; break;if (mgij=0) find=1;if (find=1) /* 找到了下一個可走方塊 */Stacktop.di=di; /* 修改原棧頂元素的 di 值*/top+;/*下一個可走方塊進(jìn)棧 */Stacktop.i=i; Stacktop.j=j; Stacktop.di=-1;mgij=-1; /* 避免重復(fù)走到該方塊 */else/*沒有路徑可走 ,則退棧 */ mgStacktop.iStacktop.j=0;/*讓該位置變?yōu)槠渌?路徑可走方塊 *