《c語(yǔ)言實(shí)現(xiàn)迷宮問(wèn)題#僅供借鑒》由會(huì)員分享，可在線閱讀，更多相關(guān)《c語(yǔ)言實(shí)現(xiàn)迷宮問(wèn)題#僅供借鑒(20頁(yè)珍藏版)》請(qǐng)?jiān)谌巳宋膸?kù)網(wǎng)上搜索。

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

2、態(tài)，數(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、通過(guò)迷宮的路徑，就必須進(jìn)行試探性搜索，只要有路可走就前進(jìn)一步，無(wú)路可進(jìn)，換一個(gè)方向進(jìn)行嘗試；當(dāng)所有方向均不可走時(shí)，則沿原路退回一步(稱(chēng)為回溯)，重新選擇未走過(guò)可走的路，如此繼續(xù)，直至到達(dá)出口或返回入口(沒(méi)有通路)。在探索前進(jìn)路徑時(shí)，需要將搜索的蹤跡記錄下來(lái)，以便走不通時(shí)，可沿原路返回到前一個(gè)點(diǎn)換一個(gè)方向再進(jìn)行新的探索。后退的嘗試路徑與前進(jìn)路徑正好相反，因此可以借用一個(gè)棧來(lái)記錄前進(jìn)路徑。方向：每一個(gè)可通點(diǎn)有4個(gè)可嘗試的方向，向不同的方向前進(jìn)時(shí)，目的地的坐標(biāo)不同。預(yù)先把4個(gè)方向上的位移存在一個(gè)數(shù)組中。如把上、右、下、左(即順時(shí)針?lè)较?依次編號(hào)為0、1、2、3.其增量數(shù)組move4如圖3所示。mov。

4、e4xy0-1010121030-1圖2數(shù)組move4方位示意圖如下：通路：通路上的每一個(gè)點(diǎn)有3個(gè)屬性：一個(gè)橫坐標(biāo)屬性i、一個(gè)列坐標(biāo)屬性j和一個(gè)方向?qū)傩詃i，表示其下一點(diǎn)的位置。如果約定嘗試的順序?yàn)樯稀⒂摇⑾隆⒆?即順時(shí)針?lè)较?，則每嘗試一個(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)取棧頂方塊(不退棧)若該方塊為出口，輸出所有的方塊即為路徑，其代碼和相應(yīng)解釋如下：int mgpath(int xi。

5、,int yi,int xe,int ye)/求解路徑為:(xi,yi)-(xe,ye)struct int i;/當(dāng)前方塊的行號(hào)int j;/當(dāng)前方塊的列號(hào)int di;/di是下一可走方位的方位號(hào) stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+; /初始方塊進(jìn)棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top-1)/棧不空時(shí)循環(huán)i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe & j=ye)/找到了出口,輸出路徑 printf。

6、(迷宮路徑如下:n);for (k=0;ktop=-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)被全部掃描過(guò)，無(wú)可以通的路)標(biāo)志當(dāng)前節(jié)點(diǎn)沒(méi)有往前的路后退一個(gè)節(jié)點(diǎn)搜索If(找到了目的地)輸出路徑退出循環(huán)未找到路徑 (4)輸出從入口點(diǎn)到出口點(diǎn)的一條路徑。(5)輸出標(biāo)有通路的迷宮圖。3.算法流程圖：開(kāi)始初始化迷宮，顯示迷宮初始化方向位移數(shù)組尋找迷宮中的一條出路If mazexy=0設(shè)1，1為出口該點(diǎn)數(shù)據(jù)入棧TFW。

7、hile 棧不空且dir=7 或棧空顯示通路結(jié)束圖9 算法流程圖4.程序代碼：#define M2 12 /*M2*N2為實(shí)際使用迷宮數(shù)組的大小*/#define N2 11#define maxlen M2 / 棧長(zhǎng)度#include #include#include int M=M2-2,N=N2-2;/M*N迷宮的大小typedef struct /定義棧元素的類(lèi)型int x,y,dir;elemtype;typedef struct / 定義順序棧elemtype stack maxlen;int top;sqstktp;struct moved/定義方向位移數(shù)組的元素類(lèi)型對(duì)于存儲(chǔ)坐標(biāo)。

8、增量的方向位移數(shù)組move int dx,dy;/void inimaze(int mazeN2)/初始化迷宮int i,j,num;for(i=0,j=0;itop=-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-toptop-;return(s-stacks-top+1)。

9、; /棧不空，返回棧頂元素 /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=push(s,elem);/如果可行將數(shù)據(jù)入棧if(f=false)/如果返回假，說(shuō)明棧容量不足couttop=-1)&(d。

10、ir=7)|(x=M)&(y=N)&(mazexy=-1); /循環(huán)if(s-top=-1)/若是入口，則無(wú)通路couttop)coutstacki.xstacki.ytop)cout;if(i+1)%4=0)couttop-1) /根據(jù)棧中元素的坐標(biāo)，將通路的各個(gè)點(diǎn)的值改為8elem=pop(s);i=elem.x;j=elem.y;mazeij=8;for(i=1;i#define M 5/*行數(shù)*/#define N 7/*列數(shù)*/#define MaxSize 100/*棧最多元素個(gè)數(shù)*/int mgM+1N+1=/*一個(gè)迷宮,其四周要加上均為1的外框*/1,1,1,1,1,1,1,1。

11、,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;struct int i;int j;int di; StackMaxSize,PathMaxSize;/*定義棧和存放最短路徑的數(shù)組*/int top=-1;/*棧指針*/int count=1;/*路徑數(shù)計(jì)數(shù)*/int minlen=MaxSize;/*最短路徑長(zhǎng)度*/void mgpath()/*路徑為:(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+;/*進(jìn)棧*/Stacktop.i=1;Stac。

12、ktop.j=1;Stacktop.di=-1;mg11=-1; /*初始結(jié)點(diǎn)進(jìn)棧*/while (top-1)/*棧不空時(shí)循環(huán)*/i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M-2 & j=N-2)/*找到了出口,輸出路徑*/ printf(%4d: ,count+);for (k=0;kint 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;int mgpath(int xi,in。

13、t yi,int xe,int ye)/求解路徑為:(xi,yi)-(xe,ye)struct int i;/當(dāng)前方塊的行號(hào)int j;/當(dāng)前方塊的列號(hào)int di;/di是下一可走方位的方位號(hào) stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+; /初始方塊進(jìn)棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top-1)/棧不空時(shí)循環(huán)i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe & j=ye)/找到了出口,輸出路徑 printf(迷宮。

14、路徑如下: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);/找到一條路徑后返回1find=0;while (di4 & find=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) find=1;/找到下一個(gè)可走相鄰方塊if (find=1)/找到了下一個(gè)可走方塊sttop.di=di;/修改原棧頂元素的di值top+;/下一個(gè)可走方塊進(jìn)棧sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;/避免重復(fù)走到該方塊else/沒(méi)有路徑可走,則退棧mgsttop.isttop.j=0;/讓該位置變?yōu)槠渌窂娇勺叻綁Ktop-;/將該方塊退棧return(0);/表示沒(méi)有可走路徑,返回0void main()mgpath(1,1,M,N);20參考類(lèi)別。

總結(jié)

以上是生活随笔為你收集整理的C语言迷宫如何实现多个关卡,c语言实现迷宫问题#仅供借鉴的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。