c語言實(shí)現(xiàn)迷宮問題

1、精品文檔數(shù)據(jù)結(jié)構(gòu)試驗(yàn)迷宮問題（一）基本問題仁問題描述這是心理學(xué)中的一個(gè)經(jīng)典問題。心理學(xué)家把一只老鼠從 一個(gè)無頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出 來。迷宮中設(shè)置很多障礙阻止老鼠前行，迷宮唯一的出口處 放有一塊奶酪，吸引老鼠找到出口。簡而言之，迷宮問題是解決從布置了許多障礙的通道中 尋找出路的問題。本題設(shè)置的迷宮如圖1所示。入口n迷宮四周設(shè)為墻；無填充處，為可通處。設(shè)每個(gè)點(diǎn)有四 個(gè)可通方向，分別為東、南、西、北（為了清晰，以下稱“上 下左右”）。左上角為入口。右下角為出口。迷宮有一個(gè)入 口，一個(gè)出口。設(shè)計(jì)程序求解迷宮的一條通路。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)以一個(gè)mX n的數(shù)組mg表示迷宮，每個(gè)元

2、素表示一個(gè)方 塊狀態(tài)，數(shù)組元素0和1分別表示迷宮中的通路和障礙。迷 宮四周為墻，對(duì)應(yīng)的迷宮數(shù)組的邊界元素均為1o根據(jù)題目 中的數(shù)據(jù)，設(shè)置一個(gè)數(shù)組mg如下i nt mgM+2N+2二(1,1,1,1,1,1,1,11,1,0,0,1,0,0,0,11,11,1,0,0,0,1,1,1,1,0,0,1,0,0,0,11,1,0,0,0,0, 0,0,1,1,1,1,1,1,1,1,11;在算法中用到的棧采用順序存儲(chǔ)結(jié)構(gòu)，將棧定義為Struet int i; /當(dāng)前方塊的行號(hào)int j; 當(dāng)前方塊的列號(hào)int di : /di是下一個(gè)相鄰的可走的方位號(hào) st MaxSize;/ 定義棧int top

3、二T/初始化棧3設(shè)計(jì)運(yùn)算算法要尋找一條通過迷宮的路徑，就必須進(jìn)行試探性搜索，只要有路可走就前進(jìn) 一步，無路可進(jìn)，換一個(gè)方向進(jìn)行嘗試；當(dāng)所有方向均不可走時(shí)，則沿原路退回 一步（稱為回溯），重新選擇未走過可走的路，如此繼續(xù)，直至到達(dá)出口或返回 入口（沒有通路）。在探索前進(jìn)路徑時(shí)，需要將搜索的蹤跡記錄下來，以便走不 通時(shí)，可沿原路返回到前一個(gè)點(diǎn)換一個(gè)方向再進(jìn)行新的探索。后退的嘗試路徑與 前進(jìn)路徑正好相反，因此可以借用一個(gè)棧來記錄前進(jìn)路徑。方向：每一個(gè)可通點(diǎn)有4個(gè)可嘗試的方向，向不同的方向前進(jìn)時(shí)，口的地的 坐標(biāo)不同。預(yù)先把4個(gè)方向上的位移存在一個(gè)數(shù)組中。如把上、右.下、左（即 順時(shí)針方向）依次編號(hào)為0

4、、1、2、3其增量數(shù)組move4如圖3所示。圖2數(shù)組move 4(iT, j)方位0方位3（id-1）方位1(j, j+1)方位示意圖如下:（i+1, J）方位2圖3方位圖通路：通路上的每一個(gè)點(diǎn)有3個(gè)屬性：一個(gè)橫坐標(biāo)屬性i、一個(gè)列坐標(biāo)屬性 j和一個(gè)方向?qū)傩詃i,表示其下一點(diǎn)的位置。如果約定嘗試的順序?yàn)樯?、右、下?左（即順時(shí)針方向），則每嘗試一個(gè)方向不通時(shí)，di值增1,當(dāng)d增至4時(shí)，表 示此位置一定不是通路上的點(diǎn)，從棧中去除。在找到出口時(shí)，棧中保存的就是一 條迷宮通路。（1）下面介紹求解迷宮（xi,yj）到終點(diǎn)（xe,ye）的路徑的函數(shù)：先將入口進(jìn) 棧（其初始位置設(shè)置為一1）,在棧不空時(shí)循環(huán)一

5、一取棧頂方塊（不退棧）若該 方塊為出口，輸出所有的方塊即為路徑，其代碼和相應(yīng)解釋如下： int mgpath(int xi, int yi, int xe, int ye) / 求 解 路 徑 為：(xi, yi)-> (xe, ye)structint i; int j;int di: stMaxSize; int top二T;當(dāng)前方塊的行號(hào)當(dāng)前方塊的列號(hào)/di是下一可走方位的方位號(hào)/定義棧/初始化棧指針int i, j, k, di, find; top 卄;/初始方塊進(jìn)棧st top i二xi;sttop j=yi; sttop. di=-l;mgl1=-1;while (top&

6、gt;T)/棧不空時(shí)循環(huán)i 二 st top i; j二sttop j; di 二 st top, di ; /取棧頂方塊if (i=xe && j=ye)/找到了出口，輸出路徑printf（z，迷宮路徑如下：）;for (k=0;k<=top;k+)printf ("t (%d, %d)"、st k. i, st k. j);if (k+l)%5=0)/每輸出每5個(gè)方塊后換一行printf (，znz，);printfCAn");return(1) ;/找到一條路徑后返回1否則，找下一個(gè)可走的相鄰方塊若不存在這樣的路徑，說明當(dāng)前的路徑不可能

7、 走通，也就是恢復(fù)當(dāng)前方塊為0后退棧。若存在這樣的方塊，則其方位保存在棧 頂元素中，并將這個(gè)可走的相鄰方塊進(jìn)棧（其初始位置設(shè)置為-1）求迷宮回溯過程如圖4所示繼續(xù)查找其他路徑圖4 迷宮回溯過程示意圖從前一個(gè)方塊找到相鄰可走方塊之后，再從當(dāng)前方塊找在、相鄰可走方塊，若沒有這樣 的方快，說明當(dāng)前方塊不可能是從入口路徑到出口路徑的一個(gè)方塊，則從當(dāng)前方塊回溯到前 一個(gè)方塊，繼續(xù)從前一個(gè)方塊找可走的方塊。為了保證試探的可總的相鄰方塊不是已走路徑上的方塊，如（i, j）已經(jīng)進(jìn)棧，在試探 （i+b j）的下一方塊時(shí)，又試探道（i, j）,這樣會(huì)很悲劇的引起死循環(huán)，為此，在一個(gè) 方塊進(jìn)棧后，將對(duì)應(yīng)的陀數(shù)組元素

8、的值改為-1 （變?yōu)椴豢勺叩南噜彿綁K），當(dāng)退棧時(shí)（表示 該方塊沒有相鄰的可走方塊），將其值恢復(fù)0,其算法代碼和相應(yīng)的解釋如下：find=0;while (di<4 && find=0)/找下一個(gè)可走方塊di+;switch(di)case 0:i=sttop i-l;j二sttop j;break;case 1:i=sttop i;j二sttop j+1;break;case 2：i=sttop i+l;j=sttop j;break;case 3:i=sttop i, j二sttop j-l;break;辻(mgij=0) find二1;/找到下一個(gè)可走:相鄰方塊 if

9、 (find=l)sttop di=di;top+;/找到了下一個(gè)可泄方塊/修改原棧頂元素的di值/下一個(gè)可走方塊進(jìn)棧sttop i=i;sttop, j二j;sttop di=-l;mgi j二T;/避免重復(fù)上到該方塊AHA12GAGGAGAGGAFFFFAFAFelse/沒有路徑可總，則退棧mgsttopL i stLtop. j：二0;/讓該位置變?yōu)橛⑺窂娇啥ǚ綁K top;/將該方塊退棧return(0); 表示沒有可泄路徑，返回0(2)求解主程序建立主函數(shù)調(diào)用上面的算法，將mg和st棧指針定義為全局變疑void mainOmgpath(l, 1, M, N);3界面設(shè)計(jì)設(shè)訃很簡單的界

10、而，輸出路徑4運(yùn)行結(jié)果圖5?；具\(yùn)行結(jié)果(二)8個(gè)方向的問題1.設(shè)計(jì)思想(1) 設(shè)置一個(gè)迷宮節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。(2) 建立迷宮圖形。（3）對(duì)迷宮進(jìn)行處理找出一條從入口點(diǎn)到出口點(diǎn)的路徑。（4）輸出該路徑。（5）打印通路迷宮圖。圖6功能結(jié)構(gòu)圖當(dāng)迷宮采用二維數(shù)組表示時(shí)，老鼠在迷宮任一時(shí)刻的位置可山數(shù)組的行列序 號(hào)i, j來表示。而從i, j位置出發(fā)可能進(jìn)行的方向見下圖7.如果i, j 周圍的位置均為0值，則老鼠可以選擇這8個(gè)位置中的任一個(gè)作為它的下一位置。 將這8個(gè)方向分別記作：E （東）、SE （東南）、S （南）SW （西南）W （西）、NW （西北）、N （北）和NE （東北）。但是并非每一個(gè)位

11、置都有8個(gè)相鄰位置。如果 i, j位于邊界上，即匸1,或i=m,或j二1,或j二n,則相鄰位置可能是3個(gè) 或5個(gè)為了避免檢查邊界條件，將數(shù)組四周圍用值為1的邊框包圍起來，這樣二 維數(shù)組maze應(yīng)該聲明為mazem+2, n+2在迷宮行進(jìn)時(shí)，可能有多個(gè)行進(jìn)方向 可選，我們可以規(guī)定方向搜索的次序是從東（E）沿順時(shí)針方向進(jìn)行。為了簡化 問題，規(guī)定i,j的下一步位置的坐標(biāo)是x,y,并將這8個(gè)方位傷的x和y 坐標(biāo)的增量預(yù)先放在一個(gè)結(jié)構(gòu)數(shù)組move8中（見圖8）。該數(shù)組的每個(gè)分量有兩 個(gè)域dx和dy。例如要向東走，只要在j值上加上dy,就可以得到下一步位置 的x, y值為i, j+dy。于是搜索方向的變化

12、只要令方向值dir從0增至7, 便可以從move數(shù)組中得到從i, j點(diǎn)岀發(fā)搜索到的每一個(gè)相鄰點(diǎn)x,y。x二i+movedir, dxy=j+movedir. dy/F1圖7方向位移圖圖8向量差圖為了防止重走原路，我們規(guī)定對(duì)已經(jīng)走過的位置，將原值為0改為-1,這既 可以區(qū)別該位置是否已經(jīng)走到過，乂可以與邊界值1相區(qū)別。當(dāng)整個(gè)搜索過程結(jié) 束后可以將所有的-1改回到0,從而恢復(fù)迷宮原樣。這樣計(jì)算機(jī)走迷宮的方法是：采取一步一步試探的方法。每一步都從（E） 開始，按順時(shí)針對(duì)8個(gè)方向進(jìn)行探測(cè)，若某個(gè)方位上的mazeEx, y=0,表示可 以通行，則走一步；若mazex,y二1,表示此方向不可通行須換方向再

13、試。直 至8個(gè)方向都試過，mazeW, y均為1,說明此步已無路可走，需退回一步， 在上一步的下一個(gè)方向重新開始探測(cè)。為此需要設(shè)置一個(gè)棧，用來記錄所走過的 位置和方向（i, j, dir）o當(dāng)退回一步時(shí)，就從棧中退出一個(gè)元素，以便在上一個(gè)位置的下一個(gè)方向上 探測(cè)，如乂找到一個(gè)行進(jìn)方向，則把當(dāng)前位置和新的方向重新進(jìn)棧，并走到新的 位置。如果探測(cè)到x二m, y二n,則已經(jīng)到達(dá)迷宮的出口，可以停止檢測(cè)，輸出存 在棧中的路徑；若在某一位置的8個(gè)方向上都堵塞，則退回一步，繼續(xù)探測(cè)，如 果已經(jīng)退到迷宮的入口（棧中無元素），則表示此迷宮無路徑可通行。2系統(tǒng)算法（偽代碼描述）：（1）建立迷宮節(jié)點(diǎn)的結(jié)構(gòu)類型st

14、ack。（2）入迷宮圖形0表示可以通1表示不可以通。用二維數(shù)組mazeEm+2 n+2 進(jìn)行存儲(chǔ)。數(shù)組四周用1表示墻壁，其中入口點(diǎn)（1, 1）與出口點(diǎn)（m, n）固定。（3）函數(shù)path（）對(duì)迷宮進(jìn)行處理，從入口開始：While（! （s->top-l）&&（dir>=7） （x二二M）&&（y二二）&&（mazex y二二-1）For （掃描八個(gè)可以走的方向）If（找到一個(gè)可以走的方向）進(jìn)入棧標(biāo)志在當(dāng)前點(diǎn)可以找到一個(gè)可以走的方向避免重復(fù)選擇mazex y=l不再對(duì)當(dāng)前節(jié)點(diǎn)掃描If （八個(gè)方向已經(jīng)被全部掃描過，無可以通的路）標(biāo)志當(dāng)前節(jié)

15、點(diǎn)沒有往前的路后退一個(gè)節(jié)點(diǎn)搜索If （找到了目的地）輸出路徑退出循環(huán)未找到路徑(4) 輸出從入口點(diǎn)到岀口點(diǎn)的一條路徑。(5) 輸出標(biāo)有通路的迷宮圖。3. 算法流程圖：圖9算法流程圖4. 程序代碼：define M2 12 /*M2*N2為實(shí)際使用迷宮數(shù)組的大小*/#define N2 11ttdefine maxlen M2 / 棧長度include <stdio. h>#include<iostream h>#include <malloch>int M=M2-2, N=N2-2;/M*N 迷宮的大小typedef struct /上義棧元素的類型int

16、x, y, dir;/elemtype;typedef struct /泄義順序棧elemtype stack maxlen;int top;sqstktp;struct moved/立義方向位移數(shù)組的元素類型對(duì)于存儲(chǔ)坐標(biāo)增量的方向位移數(shù)組mow int dx, dy;/ /void inimaze (int maze N2)/初始化迷宮int i, j, num;for (i二0, j二0; i<=M+l; i+) /設(shè)置迷宮邊界mazei j=l;for(1=0, j=O;j<=N+l;j+)mazeij=l;for(i=M+l, j=O;j<=N+l;j+)mazeti

17、j=l;cout«"原始迷宮為:/z«endl;for(i=l;i<=M;i +)for (j=l；j<=N;j+)num= (800*(i+j)+1500) % 327;/根據(jù) MN 的值產(chǎn)生迷宮if (num<150)&&(i!=M Ij!=N)maze Lij=l;elsemazei j二0;cout«maze i j<""/顯示迷宮cout«endl;cout«endl;/inimaze/ /void inimove(struct moved moved)/初始化方向

18、位移數(shù)組/依次為 East. Southeast> south, southwest, west, northwests north, northeastmove0 dx二0;move _0 dy=l;move1 dx=l;move.l dy=l;move2 dx=l;move2 dy=O;move3 dx=l;move3 dy=-l;move4 dx二0;move4 dy=-l;move5 dx=-l;move5 dy一=1;move6 dx二一1;move6 dy=O;move7 dx=-l;move7 dy=l;/void inistack(sqstktp *s)/*初始化棧*/s

19、->top=-l;/*inistack*/int push(sqstktp*s, elemtype x)if(s->t op=max1en-1)return(false);elses->stack+s->top=x;/*棧不滿，執(zhí)行入棧操作*/return(true);/*push*/elemtype pop(sqstktp *s)/*棧頂元素出棧*/elemtype elem;if(s->top<0)/如果?？?，返回空值elem x=NULL;elem y二NULL;elem. dir二NULL;return(elem);elses->top;ret

20、urn(s->stacks->top+l);/棧不空，返回棧頂元素 /pop/ /void path(int maze N2, struct moved move, sqstktp *s)/尋找迷宮中的一條通路int i, j, dir, x, y, f; elemtype elem;i=l;j=l;dir=O;maze 1 1二-1;/設(shè)1 1為入 口 處dox=i+movedir. dx;/球下一步可行的到達(dá)點(diǎn)的坐標(biāo)y=j+movedir dy;if(mazexyj =0)elem x=i;elem. y二j;elem. dir=dir;f二push(s, elem) ;/如果

21、可行將數(shù)拯入棧if(f=false)/如果返回假，說明棧容量不足cout<<"棧長不足"；;j=y;dir=0;mazexyl =-l;elseif (dir < 7)dir+;elseelem=pop(s) ;/8個(gè)方向都不行，回退if(elem.x!=NULL)i=elem. x;j二elem. y;dir=elem dir+1;while(! (s->top=-l)&&(dir>=7) I ! (x=M)&&(y=N)&&(mazex y =-l);/循環(huán)if(s->top=-l)/若

22、是入口，則無通路cout<<"此迷宮不通"；elseelem. x=x; elem. y=y; elem. dir=dir;/將岀口坐標(biāo)入棧f=push(s, elem);cout«/z迷宮通路是："«endl;i 二0;while (i <= s->top)cout<<" (*«s->stackij. x<<", "«s->stacki y«z/)"/顯示迷宮通路 if(i!=s->top)cout<&

23、lt;z，>"if(i+l)%4=0)cout<<endl;i+；/ void draw(int maze N2, sqstktp *s)/在迷宮中繪制出通路cout<<"逃逸路線為："<Xendl;int i, j；elemtype elem;for (i=l; id; i+)/將迷宮中全部的-1值回復(fù)為0值for(j=l;j<=N;j+)if (maze iZ j=T) mazeij二0;while(s->top>-l)根據(jù)棧中元素的坐標(biāo)，將通路的各個(gè)點(diǎn)的值改為8elem=pop(s);i=elem. x;

24、j=elem. y;mazei j二8;for(i=l;i<=M;i+)for(j=l;j<=N;j+)printf ("%3d",mazei j);顯示已標(biāo)記通路的迷宮cout«endl;void mainO/尋找迷宮通路程序sqstktp *s;int maze M2 N2;struct moved move_8;inimaze(maze) ;/初始化迷宮數(shù)組s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s);/初始化棧inimove (move) ;/初始化方向位移數(shù)組path (maze, move,

25、 s) ;/尋找迷宮通路/繪制作出通路標(biāo)記的迷宮cout«endl; draw (maze, s);5. 運(yùn)行結(jié)果10101P：新建文件夾 DebugCpp8方向10 10 110 10 010 0 1010 10 1迷宮通路是，<1.1>一一XI.2>一一><23>一一一一><4.5>><5.&>><5.7>><6.8>><7,9>><8,8>><9.9>><10.9>逃逸路線為S «1

26、£81031910 18 110 0 10 a 1 0 0 110 10 0a 1 0 1 010 100 10 118 101001018188Fi*es：s any keyto仝祁壇重町萬冋位務(wù)釵紐moue（三）求所有通路和最短路徑的算法1.源代碼（用原題的數(shù)據(jù)）#include <stdio. h>/*行數(shù)*/*列數(shù)*/*棧最多元素個(gè)數(shù)*/* 一個(gè)迷宮，其四周要加上均為1的外框*/#define M 5#define N 7define MaxSize 100 int mgM+lN+l= 1,1,1,1,1,1,1,1,1,0, 0,1,0, 0, 0,1, 1,1

27、,0, 0, 0,1, 1,1, 1,0, 0, to, 0, 0,1,1,0, 0, 0, 0, 0, 0,1, 1,1,1,1,1,1,1,1;structint i;int j;int di;int top=-l;int count=l;int minlen=MaxSize; void mgpath()? StackMaxSize, PathMaxSize; /*定義棧和存放最短路徑的數(shù)組*/*棧指針*/*路徑數(shù)計(jì)數(shù)*/*最短路徑長度*/*路徑為：(1,1)->(M-2,N-2)/int i, j, di, find, k;top+；/* 進(jìn)棧 */Stacktop_ i=l;St

28、acktop. j=l;Stack topi. di=-l;mgl 1=-1; /* 初始結(jié)點(diǎn)進(jìn)棧 */ wh訂e (top>-l)/*棧不空時(shí)循環(huán)*/i=Stacktop i;j二Stacktop j;di=Stacktop di; if (i=M-2 && j=N-2) /*找到了出口，輸岀路徑*/printf C?%4d:"、count+);for (k=0;k<=top;k卄)printf C (%d, %d)”、Stack kJ. i, Stack kJ. j);辻(k+l)%5=0) printf rnt3;/*輸出時(shí)每5個(gè)結(jié)點(diǎn)換一行*/pri

29、ntf("n");if (top+l<minlen)/*比較找最短路徑*/for (k=0;k<=top;k+)Pathk=Stackk;minlen=top+l;mg Stack Itop. i Stack top, j二0;/*讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn)top;i二Stacktop i;j二Stacktop j;di二Stacktop di; find=0;while (di<4 && find=0) /*找下一個(gè)可走結(jié)點(diǎn)*/di+;switch(di)case 0:i=Stacktop i-l;j二Stacktop j;break;

30、 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-l;break;if (mgi j=0) find二 1;if (find=l)/*找到了下一個(gè)可走結(jié)點(diǎn)*/ StacktopL di=di;/*修改原棧頂元素的di值*/top+ ； Stack top. i二 i; Stack top. j=j; Stack top, di 二-1;/* F一個(gè)可走結(jié) 點(diǎn)進(jìn)棧*/mgi/*避免重復(fù)走到該結(jié)點(diǎn)*/else/*沒

31、有路徑可走，則退棧*/mg Stack top, i Stacktop. j二0;/*讓該位It變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn)*/top;printf (”最短路徑如下：)；printf ("長度：%dn，z, minlen);printf (，?路徑：”)；for (k=0:k<minlen:k+)printf C (%d, %d)", Pathk. i, Pathk. j);if (k+1用5=0) printfCW); /*輸岀時(shí)每5個(gè)結(jié)點(diǎn)換一行*/printf("n");void mainOprintf (”迷宮所有路徑如下:n");mgp

32、athO ;2求解結(jié)果6. 實(shí)驗(yàn)收獲及思考這次試驗(yàn)總體來說還是比較簡單的，因?yàn)閮簜€(gè)思考問題都是在基本問題的源代 碼上進(jìn)行改進(jìn)和補(bǔ)充。有了第一次數(shù)據(jù)結(jié)構(gòu)編程和測(cè)試的經(jīng)驗(yàn)，這次試驗(yàn)減少了 很多困難，相對(duì)來說容易多了。附錄基本問題換代碼（思考問題源代碼在上文中已經(jīng)全部給出）define M 4#define N 6define MaxSize 100include <stdio. h>int mgM+2N+2=1,1,1,1,1,1,1,1,1,0, 0, to, 0, 0,1,1,1,0, 0, 0,1, 1,1,1,0, 0, to, 0, 0,1 t1,0, 0, 0, 0, 0, 0,1 t1,1,1,1,1,1,1,1;int mgpath(i