《求解迷宮問題(c語言,很詳細哦》由會員分享，可在線閱讀，更多相關《求解迷宮問題(c語言,很詳細哦(5頁珍藏版)》請在人人文庫網上搜索。

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

2、方塊是通道 , 為 1 時表示對應方塊為墻 , 如圖 3.3 所示的迷 宮, 對應的迷宮數組 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 ;偽代碼：5 / 5c 語言描述如下：v。

3、oid mgpath() /* 路徑為 :(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+; /* 初始方塊進棧 */Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while (top-1) /* 棧不空時循環 */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);printf(n);return;find=0;while (di4 & find=0) /*找下一個可走方塊 */ 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;if (mgij=0) find=1;if (find=1) /*找到了下一個可走方塊 */Stacktop.di=di; /* 修改原棧頂元素的 di 值 */ top+; /* 下一個可走方塊進棧 */ Stacktop.i=i; Stacktop.j=j;Stacktop.di=-1; mgij=-1; /* 避免重復走到該方塊 */ else /* 沒有路徑可走 , 則退棧 */ mgStacktop.iStacktop.j=0;/* 讓該位置變為其他 路徑可走方塊 */top-;printf( 沒有可走路徑 !n。