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

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

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

3、一條通過迷宮的路徑，就必須進(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、1、2、3.其增量數(shù)組move4

4、如圖3所示。move4 x y圖2數(shù)組move4力位3<,j-1)方位1(J. J+l>方位示意圖如下:（i+lP 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)解釋如下：數(shù)據(jù)結(jié)構(gòu)試驗(yàn)迷宮問題int mgpath(int xi,int yi,int xe,int ye)/求解路徑為:(xi,yi)->(xe,ye)struct/ 當(dāng)前方塊的行號(hào)/ 當(dāng)前方塊的列號(hào)/di 是下一可走方位的方位號(hào)/ 定義棧/ 初始化棧指針/ 初始方塊進(jìn)棧int i;int j;int di; stMaxSize;int top=-1;int i,j,k,di,find;/ 棧不空時(shí)循環(huán)top+; sttop.i=xi;sttop.j=yi; sttop.di=-1;mg11=-1; while (top>

6、-1) i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe && j=ye)/ 找到了出口 , 輸出路徑 printf(" 迷宮路徑如下 :n");for (k=0;k<=top;k+)printf("t(%d,%d)",stk.i,stk.j);if (k+1)%5=0)/ 每輸出每 5 個(gè)方塊后換一行printf("n");printf("n");return(1); / 找到一條路徑后返回 1 否則，找下一個(gè)可走的相鄰方塊若不存在這樣的路徑，

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

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

9、in d=1;找到下一個(gè)可走相鄰方塊if (fin d=1)找到了下一個(gè)可走方塊sttop.di=di;修改原棧頂元素的 di值top+;/下一個(gè)可走方塊進(jìn)棧sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;避免重復(fù)走到該方塊 else/沒有路徑可走，則退棧mgsttop.isttop.j=0;讓該位置變?yōu)槠渌窂娇勺叻綁Ktop-;將該方塊退棧return(O); /表示沒有可走路徑，返回0(2)求解主程序建立主函數(shù)調(diào)用上面的算法，將mg和st棧指針定義為全局變量void mai n()mgpath(1,1,M,N);3界面設(shè)計(jì)設(shè)計(jì)很簡(jiǎn)單的界面，輸出路徑4運(yùn)行結(jié)果

10、圖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è)位置都有8個(gè)相鄰位置。如果i,

11、j 位于邊界上，即i=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)行。為了簡(jiǎ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+dy。于是搜索方向的變化只要令方向值dir從0增至7，便可以從

12、move數(shù)組中得到從i,j點(diǎn)出發(fā)搜索到的每一個(gè)相鄰點(diǎn)x,y。x=i+movedir.dxy=j+movedir.dyy/1r圖7方向位移圖22 1Ip |1 丁21+? 松2-I*3-2dx dy圖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è)方位上的mazex,y=0，表示可以 通行，則走一步；若mazex,y=1，表示此方向不可通

13、行須換方向再試。直至8個(gè)方向都試過，mazex,y均為1，說明此步已無路可走，需退回一步，在上一 步的下一個(gè)方向重新開始探測(cè)。為此需要設(shè)置一個(gè)棧，用來記錄所走過的位置和 方向（i，j，dir）。當(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)類型

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

15、通的路)標(biāo)志當(dāng)前節(jié)點(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 11#define maxlen M2 / 棧長(zhǎng)度#include <stdio.h> #include<iostream.h> #include <malloc.h>int M=M2-2,N=N2-2;/M*N 迷宮的大小typedef struct /

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

17、eij=1;cout<<" 原始迷宮為： "<<endl;for(i=1;i<=M;i+)for (j=1;j<=N;j+) num=(800*(i+j)+1500) % 327;/ 根據(jù) MN 的值產(chǎn)生迷宮 if (num<150)&&(i!=M|j!=N)mazeij=1;else mazeij=0;cout<<mazeij<<" "/ 顯示迷宮 cout<<endl; cout<<endl;/inimaze / void inimove(str

18、uct moved move)/ 初始化方向位移數(shù)組northeast/ 依次為 East， Southeast， south， southwest， west， northwest ， north ， move0.dx=0;move0.dy=1;move1.dx=1;move1.dy=1;move2.dx=1;move2.dy=0; move3.dx=1;move3.dy=-1;move4.dx=0;move4.dy=-1; move5.dx=-1;move5.dy-=1;move6.dx=-1;move6.dy=0;move7.dx=-1;move7.dy=1;/void inistack

19、(sqstktp *s) /* 初始化棧 */s->top=-1; /*inistack*/int push(sqstktp*s,elemtype x) if(s->top=maxlen-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;

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

21、ush(s,elem);/ 如果可行將數(shù)據(jù)入棧 if(f=false)/ 如果返回假，說明棧容量不足 cout<<" 棧長(zhǎng)不足 "i=x;j=y;dir=0;mazexy=-1;elseif (dir < 7) dir+;else elem=pop(s); /8 個(gè)方向都不行，回退 if(elem.x!=NULL)i=elem.x;j=elem.y; dir=elem.dir+1; while(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1);/ 循

22、環(huán)if(s->top=-1)/ 若是入口，則無通路cout<<" 此迷宮不通 "elseelem.x=x; elem.y=y; elem.dir=dir;/ 將出口坐標(biāo)入棧 f=push(s,elem);cout<<" 迷宮通路是： "<<endl;i=0;while (i <= s->top)cout<<"("<<s->stacki.x<<","<<s->stacki.y<<")

23、"/ 顯示迷宮通路 if(i!=s->top)cout<<"->"if(i+1)%4=0)cout<<endl;i+;/void draw(int mazeN2,sqstktp *s)/在迷宮中繪制出通路cout<<" 逃逸路線為： "<<endl;int i,j;elemtype elem;for(i=1;i<=M;i+)/將迷宮中全部的 -1 值回復(fù)為 0 值 for(j=1;j<=N;j+)if(mazeij=-1) mazeij=0;while(s->top&

24、gt;-1)/ 根據(jù)棧中元素的坐標(biāo)， 將通路的各個(gè)點(diǎn)的值改為 8elem=pop(s);i=elem.x;j=elem.y; mazeij=8; for(i=1;i<=M;i+)for(j=1;j<=N;j+)printf("%3d",mazeij);/ 顯示已標(biāo)記通路的迷宮cout<<endl;void main()/ 尋找迷宮通路程序sqstktp *s;int mazeM2N2;struct moved move8;數(shù)據(jù)結(jié)構(gòu)試驗(yàn)一一迷宮問題/初始化迷宮數(shù)組/初始化棧/初始化方向位移數(shù)組/尋找迷宮通路/繪制作出通路標(biāo)記的迷宮ini maze(ma

25、ze);s=(sqstktp *)malloc(sizeof(sqstktp); in istack(s);inimo ve(move); path(maze,move,s); cout<<e ndl;draw(maze,s);5.運(yùn)行結(jié)果新建文件夾 C2)DebugCppB右向.exe*|01 « 1r 1 n n 1191010 0 18P 101i a i 00 10 00 0 10 110 1010 L 011 U U 1w 1 w 100 0 10X 0 L 00迂百通路是.<1 ” 1 >一XI ”2一一C23一一一一C4.S>>C5.

26、6>>CS.?>>C6.8>>C7,9>e>>C9,9>>C10,9>謹(jǐn)逸路線為:U H 1M 1 k) L b 1。丄E丄巧丄0101_ 0 1a ±0±0 a0 101 8 ± » 0 11_ 0 1a ±» s ±0n 101 n p i ft 1191301018910a i 0 i s 11 a a10 10 18a a i01 B 108JKi'ess： any Jc呂屮 ca continuie仝標(biāo)增童旳萬冋位移敢爼耐斥（三）求所有

27、通路和最短路徑的算法#i nclude <stdio.h>#defi ne M 5#defi ne N 7#defi ne MaxSize 100 int mgM+1N+1= 1,1,1,1,1,1,1,1,1,0,0,1,000,1,1,1,000,1,1,1,1,0,0,1,0,0,0,1,1源代碼（用原題的數(shù)據(jù)）/*行數(shù)*/*列數(shù)*/*棧最多元素個(gè)數(shù)*/*一個(gè)迷宮，其四周要加上均為1的外框*/*棧指針 */* 路徑數(shù)計(jì)數(shù) */* 最短路徑長(zhǎng)度 */* 路徑為 :(1,1)->(M-2,N-2)*/*進(jìn)棧 */while (top>-1)/* 棧不空時(shí)循環(huán) */1,

28、0,0,0,0,0,0,1,1,1,1,1,1,1,1,1 ;structint i;int j;int di; StackMaxSize,PathMaxSize; /* 定義棧和存放最短路徑的數(shù)組 */ int top=-1;int count=1;int minlen=MaxSize;void mgpath()int i,j,di,find,k; top+; Stacktop.i=1; Stacktop.j=1;Stacktop.di=-1;mg11=-1; /* 初始結(jié)點(diǎn)進(jìn)棧 */i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M-2 &am

29、p;& j=N-2) /* 找到了出口 ,輸出路徑 */printf("%4d: ",count+);for (k=0;k<=top;k+) printf("(%d,%d) ",Stackk.i,Stackk.j);if (k+1)%5=0) printf("nt");/*輸出時(shí)每 5 個(gè)結(jié)點(diǎn)換一行 */* 比較找最短路徑 */* 讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn) */ printf("n");if (top+1<minlen)for (k=0;k<=top;k+) Pathk=Stackk;

30、minlen=top+1;mgStacktop.iStacktop.j=0;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-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=S

31、tacktop.j-1;break;if (mgij=0) find=1;if (find=1)/* 找到了下一個(gè)可走結(jié)點(diǎn) */ Stacktop.di=di;/* 修改原棧頂元素的 di 值 */top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/* 下一個(gè)可走結(jié)點(diǎn)進(jìn)棧 */ mgij=-1; /* 避免重復(fù)走到該結(jié)點(diǎn) */else /* 沒有路徑可走 ,則退棧 */mgStacktop.iStacktop.j=0;/* 讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn) */top-;printf(" 最短路徑如下 :n");printf("

32、; 長(zhǎng)度 : %dn",minlen);printf(" 路徑 : ");for (k=0;k<minlen;k+)printf("(%d,%d) ",Pathk.i,Pathk.j);if (k+1)%5=0) printf("nt");/*輸出時(shí)每 5 個(gè)結(jié)點(diǎn)換一行 */printf("n");void main()printf(" 迷宮所有路徑如下 :n");mgpath();2 求解結(jié)果數(shù)據(jù)結(jié)構(gòu)試驗(yàn)一一迷宮問題6實(shí)驗(yàn)收獲及思考這次試驗(yàn)總體來說還是比較簡(jiǎn)單的，因?yàn)閹讉€(gè)思考問題都是在基本問題的源代 碼上進(jìn)行改進(jìn)和補(bǔ)充。有了第一次數(shù)據(jù)結(jié)構(gòu)編程和測(cè)試的經(jīng)驗(yàn)，這次試驗(yàn)減少了 很多困難，相對(duì)來說容易多了。附錄基本問題換代碼（思考問題源代碼在上文中已經(jīng)全部給出）#defi ne M 4#defi ne N 6#defi ne MaxSize 100#i nclude <stdio.h>int mgM+2N+2=1,