《c語言實作迷宮問題》由會員分享，可線上閱讀，更多相關《c語言實作迷宮問題(21頁珍藏版)》請在人人文庫網上搜尋。
1、資料結構試驗迷宮問題(一)基本問題1.問題描述這是心理學中的一個經典問題。心理學家把一隻老鼠從一個無頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出來。迷宮中設定很多障礙阻止老鼠前行，迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。簡而言之，迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。本題設定的迷宮如圖1所示。圖1 迷宮示意圖迷宮四周設為牆；無填充處，為可通處。設每個點有四個可通方向，分别為東、南、西、北(為了清晰，以下稱“上下左右”)。左上角為入口。右下角為出口。迷宮有一個入口，一個出口。設計程式求解迷宮的一條通路。2.資料結構設計以一個mn的數組mg表示迷宮，每個元素表示一個方塊狀。
2、态，數組元素0和1分别表示迷宮中的通路和障礙。迷宮四周為牆，對應的迷宮數組的邊界元素均為1。根據題目中的資料，設定一個數組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;在算法中用到的棧采用順序存儲結構，将棧定義為Struct int i; /目前方塊的行号int j; /目前方塊的列号int di; /di是下一個相鄰的可走的方位号stMaxSize;/ 定義棧精品.int top=-1 /初始化棧3設計運算算法要尋。
3、找一條通過迷宮的路徑，就必須進行試探性搜尋，隻要有路可走就前進一步，無路可進，換一個方向進行嘗試；當所有方向均不可走時，則沿原路退回一步(稱為回溯)，重新選擇未走過可走的路，如此繼續，直至到達出口或傳回入口(沒有通路)。在探索前進路徑時，需要将搜尋的蹤迹記錄下來，以便走不通時，可沿原路傳回到前一個點換一個方向再進行新的探索。後退的嘗試路徑與前進路徑正好相反，是以可以借用一個棧來記錄前進路徑。方向：每一個可通點有4個可嘗試的方向，向不同的方向前進時，目的地的坐标不同。預先把4個方向上的位移存在一個數組中。如把上、右、下、左(即順時針方向)依次編号為0、1、2、3.其增量數組move4如圖3所示。。
4、move4xy0-1010121030-1圖2數組move4方位示意圖如下：通路：通路上的每一個點有3個屬性：一個橫坐标屬性i、一個列坐标屬性j和一個方向屬性di，表示其下一點的位置。如果約定嘗試的順序為上、右、下、左(即順時針方向)，則每嘗試一個方向不通時，di值增1，當d增至4時，表示此位置一定不是通路上的點，從棧中去除。在找到出口時，棧中儲存的就是一條迷宮通路。(1)下面介紹求解迷宮(xi,yj)到終點(xe,ye)的路徑的函數：先将入口進棧(其初始位置設定為1)，在棧不空時循環取棧頂方塊(不退棧)若該方塊為出口，輸出所有的方塊即為路徑，其代碼和相應解釋如下：精品.int mgpath(。
5、int xi,int yi,int xe,int ye)/求解路徑為:(xi,yi)-(xe,ye)struct int i;/目前方塊的行号int j;/目前方塊的列号int di;/di是下一可走方位的方位号 stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+; /初始方塊進棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top-1)/棧不空時循環i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe & j=ye)/找到了出口,輸出路徑 。
6、printf(迷宮路徑如下:n);for (k=0;ktop=-1)&(dir=7)|(x=M)&(y=N)&(mazexy=-1)For(掃描八個可以走的方向)If(找到一個可以走的方向)進入棧标志在目前點可以找到一個可以走的方向避免重複選擇mazexy=-1不再對目前節點掃描If(八個方向已經被全部掃描過，無可以通的路)标志目前節點沒有往前的路後退一個節點搜尋If(找到了目的地)精品.輸出路徑退出循環未找到路徑 (4)輸出從入口點到出口點的一條路徑。(5)輸出标有通路的迷宮圖。3.算法流程圖：精品.開始初始化迷宮，顯示迷宮初始化方向位移數組尋找迷宮中的一條出路If mazexy=0設1，1。
7、為出口該點資料入棧TFWhile 棧不空且dir=7 或棧空顯示通路結束圖9 算法流程圖4.程式代碼：#define M2 12 #define N2 11#define maxlen M2 / 棧長度#include #include#include int M=M2-2,N=N2-2;/M*N迷宮的大小typedef struct /定義棧元素的類型精品.int x,y,dir;elemtype;typedef struct / 定義順序棧elemtype stack maxlen;int top;sqstktp;struct moved/定義方向。
8、位移數組的元素類型對于存儲坐标增量的方向位移數組move int dx,dy;/void inimaze(int mazeN2)/初始化迷宮int i,j,num;for(i=0,j=0;itop=-1; int push(sqstktp*s,elemtype x)if(s-top=maxlen-1)return(false);elses-stack+s-top=x;return(true);elemtype pop(sqstktp *s)elemtype elem;if(s-toptop-;return(。
9、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; /設11為入口處do x=i+movedir.dx;/球下一步可行的到達點的坐标y=j+movedir.dy;if(mazexy=0)elem.x=i;elem.y=j;elem.dir=dir;f=push(s,elem);/如果可行将資料入棧if(f=false)/如果傳回假，說明棧。
10、容量不足couttop=-1)&(dir=7)|(x=M)&(y=N)&(mazexy=-1); /循環if(s-top=-1)/若是入口，則無通路couttop)coutstacki.xstacki.ytop)cout;if(i+1)%4=0)couttop-1) /根據棧中元素的坐标，将通路的各個點的值改為8elem=pop(s);i=elem.x;j=elem.y;mazeij=8;for(i=1;i#define M 5#define N 7#define MaxSize 100int mgM+1N+1=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;struct 精品.int i;int j;int di; StackMaxSize,PathMaxSize;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; while (top-1)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,。
13、1,1;int mgpath(int xi,int yi,int xe,int ye)/求解路徑為:(xi,yi)-(xe,ye)struct int i;/目前方塊的行号int j;/目前方塊的列号int di;/di是下一可走方位的方位号 stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+; /初始方塊進棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top-1)/棧不空時循環i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe & j=。
14、ye)/找到了出口,輸出路徑 printf(迷宮路徑如下:n);for (k=0;k=top;k+)printf(t(%d,%d),stk.i,stk.j);if (k+1)%5=0)/每輸出每5個方塊後換一行printf(n); printf(n);return(1);/找到一條路徑後傳回1find=0;while (di4 & find=0)/找下一個可走方塊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;brea。
15、k;case 3:i=sttop.i,j=sttop.j-1;break;if (mgij=0) find=1;/找到下一個可走相鄰方塊if (find=1)/找到了下一個可走方塊精品.sttop.di=di;/修改原棧頂元素的di值top+;/下一個可走方塊進棧sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;/避免重複走到該方塊else/沒有路徑可走,則退棧mgsttop.isttop.j=0;/讓該位置變為其他路徑可走方塊top-;/将該方塊退棧return(0);/表示沒有可走路徑,傳回0void main()mgpath(1,1,M,N);如有侵權請聯系告知删除，感謝你們的配合！精品。