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

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

2、對(duì)應(yīng)方塊是通道 , 為 1 時(shí)表示對(duì)應(yīng)方塊為墻 , 如圖 3.3 所示的迷宮, 對(duì)應(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。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 ;偽代碼：c 語言描述如下：。2

3、。void mgpath() /*路徑為 :(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+; /*初始方塊進(jìn)棧 */Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while (top-1)/* 棧不空時(shí)循環(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 (

4、k+1)%5=0)printf(n);。3。printf(n);return;find=0;while (di4 & find=0) /*找下一個(gè)可走方塊 */di+;switch(di)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;。4。if (mgij=0) find=1;if (find=1) /*找到了下一個(gè)可走方塊*/Stacktop.di=di;/* 修改原棧頂元素的di 值*/top+;/* 下一個(gè)可走方塊進(jìn)棧*/Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;mgij=-1; /*避免重復(fù)走到該方塊*/else/* 沒有路徑可走 , 則退棧 */mgStacktop.iStacktop.j=0;/* 讓該位置變?yōu)槠渌窂娇勺叻綁K */top-;pr