求解迷宮問(wèn)題(c語(yǔ)言,很詳細(xì)哦)

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

2、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,0,0,0,0,1,1,0,0,1, 1,0,1,1,1,0,000,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é)束；mi/此時(shí)棧中存放的是一條從入口位置到出口位置的路徑 否則切換當(dāng)前位置的北鄰方塊!為新的當(dāng)前位置，否則若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊星 若棧不空但棧頂位置的四周均不可通，I'Ji貝!1刪去棧頂位置；/從路徑中刪去該通道塊若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？眨籧語(yǔ)言描述如下:wordvoid mgpath() /* 路徑為：(1,1)->(M-2,N-2)*/int i,j,di,fi nd,k;top+; /*初始方塊進(jìn)棧*/S

4、tackto p.i=1;Stackto p.j=1;Stackto p.di=-1;mg11=-1;while (to p>-1)/*棧不空時(shí)循環(huán)*/i=Stackto p.i;j=Stackt op .j;di=Stackt op .di;if (i=M-2 && j=N-2) /*找到了出口，輸出路徑*/printf（"迷宮路徑如下:n"）;for (k=0;k<=t op ;k+) prin tf("t(%d,%d)",Stackk.i,Stackk.j);if (k+1)%5=0)prin tf("n&qu

5、ot;);wordprin tf("n");return;fin d=0;找下一個(gè)可走方塊*/while (di<4 && fin d=0) /*di+;switch(di) case 0:i=Stackt op .i-1;-1;j=Stackt op .j;break;case 1:i=Stackt op .i;j=Stackto p.j+1;break;case 2:i=Stackt op .i+1;j=Stackt op .j;break;case 3:i=Stackt op .i;j=Stackt op.jbreak;wordif (mgij=0) fin d=1;if (find=1) /*找到了下一個(gè)可走方塊*/Stackto p.di二di;/*修改原棧頂元素的di值*/top+;/*下一個(gè)可走方塊進(jìn)棧*/Stackt op .i二i;Stackto p.j二j;Stackt op .di=-1;elsemgij=-1; /*/*沒(méi)有路徑可走避免重復(fù)走到該方塊*/,則退棧*