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

《c語言實現(xiàn)迷宮問題》由會員分享，可在線閱讀，更多相關《c語言實現(xiàn)迷宮問題（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

. 數(shù)據(jù)結構試驗——迷宮問題 （一）基本問題 1.問題描述 這是心理學中的一個經典問題。心理學家把一只老鼠從一個無頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出來。迷宮中設置很多障礙阻止老鼠前行，迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。 簡而言之，迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。本題設置的迷宮如圖1所示。 圖1 迷宮示意圖 迷宮四周設為墻；無填充處，為可通處。設每個點有四個可通方向，分別為東、南、西、北(為了清晰，以下稱“上下左右”)。左上角為入口。右下角為出口。迷宮有一個入口，一個出口。設計程序求解迷宮的一條通路。 2.數(shù)據(jù)結構設計 以一個mn的數(shù)組mg表示迷宮，每個元素表示一個方塊狀態(tài)，數(shù)組元素0和1分別表示迷宮中的通路和障礙。迷宮四周為墻，對應的迷宮數(shù)組的邊界元素均為1。根據(jù)題目中的數(shù)據(jù)，設置一個數(shù)組mg如下 int mg[M+2][N+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是下一個相鄰的可走的方位號 }st[MaxSize];// 定義棧 int top=-1 //初始化棧 3設計運算算法 要尋找一條通過迷宮的路徑，就必須進行試探性搜索，只要有路可走就前進一步，無路可進，換一個方向進行嘗試；當所有方向均不可走時，則沿原路退回一步（稱為回溯），重新選擇未走過可走的路，如此繼續(xù)，直至到達出口或返回入口（沒有通路）。在探索前進路徑時，需要將搜索的蹤跡記錄下來，以便走不通時，可沿原路返回到前一個點換一個方向再進行新的探索。后退的嘗試路徑與前進路徑正好相反，因此可以借用一個棧來記錄前進路徑。 方向：每一個可通點有4個可嘗試的方向，向不同的方向前進時，目的地的坐標不同。預先把4個方向上的位移存在一個數(shù)組中。如把上、右、下、左（即順時針方向）依次編號為0、1、2、3.其增量數(shù)組move[4]如圖3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 圖2數(shù)組move[4] 方位示意圖如下： 通路：通路上的每一個點有3個屬性：一個橫坐標屬性i、一個列坐標屬性j和一個方向屬性di，表示其下一點的位置。如果約定嘗試的順序為上、右、下、左（即順時針方向），則每嘗試一個方向不通時，di值增1，當d增至4時，表示此位置一定不是通路上的點，從棧中去除。在找到出口時，棧中保存的就是一條迷宮通路。 （1）下面介紹求解迷宮（xi,yj）到終點（xe,ye）的路徑的函數(shù)：先將入口進棧（其初始位置設置為—1），在棧不空時循環(huán)——取棧頂方塊（不退棧）①若該方塊為出口，輸出所有的方塊即為路徑，其代碼和相應解釋如下： int mgpath(int xi,int yi,int xe,int ye) //求解路徑為:(xi,yi)->(xe,ye) { struct { int i; //當前方塊的行號 int j; //當前方塊的列號 int di; //di是下一可走方位的方位號 } st[MaxSize]; //定義棧 int top=-1; //初始化棧指針 int i,j,k,di,find; top++; //初始方塊進棧 st[top].i=xi;st[top].j=yi; st[top].di=-1;mg[1][1]=-1; while (top>-1) //棧不空時循環(huán) { i=st[top].i;j=st[top].j;di=st[top].di; //取棧頂方塊 if (i==xe && j==ye) //找到了出口,輸出路徑 { printf("迷宮路徑如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",st[k].i,st[k].j); if ((k+1)%5==0) //每輸出每5個方塊后換一行 printf("\n"); } printf("\n"); return(1); //找到一條路徑后返回1 } ②否則，找下一個可走的相鄰方塊若不存在這樣的路徑，說明當前的路徑不可能走通，也就是恢復當前方塊為0后退棧。若存在這樣的方塊，則其方位保存在棧頂元素中，并將這個可走的相鄰方塊進棧（其初始位置設置為-1） 求迷宮回溯過程如圖4所示 從前一個方塊找到相鄰可走方塊之后，再從當前方塊找在、相鄰可走方塊，若沒有這樣的方快，說明當前方塊不可能是從入口路徑到出口路徑的一個方塊，則從當前方塊回溯到前一個方塊，繼續(xù)從前一個方塊找可走的方塊。 為了保證試探的可走的相鄰方塊不是已走路徑上的方塊，如（i,j）已經進棧，在試探（i+1，j）的下一方塊時，又試探道（i，j），這樣會很悲劇的引起死循環(huán)，為此，在一個方塊進棧后，將對應的mg數(shù)組元素的值改為-1（變?yōu)椴豢勺叩南噜彿綁K），當退棧時（表示該方塊沒有相鄰的可走方塊），將其值恢復0，其算法代碼和相應的解釋如下： find=0; while (di<4 && find==0) //找下一個可走方塊 { di++; switch(di) { case 0:i=st[top].i-1;j=st[top].j;break; case 1:i=st[top].i;j=st[top].j+1;break; case 2:i=st[top].i+1;j=st[top].j;break; case 3:i=st[top].i,j=st[top].j-1;break; } if (mg[i][j]==0) find=1;//找到下一個可走相鄰方塊 } if (find==1) //找到了下一個可走方塊 { st[top].di=di; //修改原棧頂元素的di值 top++; //下一個可走方塊進棧 st[top].i=i;st[top].j=j;st[top].di=-1; mg[i][j]=-1; //避免重復走到該方塊 } else //沒有路徑可走,則退棧 { mg[st[top].i][st[top].j]=0;//讓該位置變?yōu)槠渌窂娇勺叻綁K top--; //將該方塊退棧 } } return(0); //表示沒有可走路徑,返回0 （2）求解主程序 建立主函數(shù)調用上面的算法，將mg和st棧指針定義為全局變量 void main() { mgpath(1,1,M,N); } 3界面設計 設計很簡單的界面，輸出路徑 4運行結果 圖5。基本運行結果 （二）8個方向的問題 1.設計思想 (1)設置一個迷宮節(jié)點的數(shù)據(jù)結構。 (2)建立迷宮圖形。 (3)對迷宮進行處理找出一條從入口點到出口點的路徑。 (4)輸出該路徑。 (5)打印通路迷宮圖。 初始化迷宮 通過隨機方法設置迷宮布局 建立并輸出迷宮原圖 搜索迷宮通路 輸出迷宮通路及路線圖 結束 圖6功能結構圖 當迷宮采用二維數(shù)組表示時，老鼠在迷宮任一時刻的位置可由數(shù)組的行列序號i，j來表示。而從 [i],[j]位置出發(fā)可能進行的方向見下圖7.如果[i],[j]周圍的位置均為0值，則老鼠可以選擇這8個位置中的任一個作為它的下一位置。將這8個方向分別記作：E（東）、SE（東南）、S（南）SW（西南）W（西）、NW（西北）、N（北）和NE（東北）。但是并非每一個位置都有8個相鄰位置。如果[i],[j]位于邊界上，即i=1，或i=m，或j=1，或j=n，則相鄰位置可能是3個或5個為了避免檢查邊界條件，將數(shù)組四周圍用值為1的邊框包圍起來，這樣二維數(shù)組maze應該聲明為maze[m+2],[n+2]在迷宮行進時，可能有多個行進方向可選，我們可以規(guī)定方向搜索的次序是從東（E）沿順時針方向進行。為了簡化問題，規(guī)定[i],[j]的下一步位置的坐標是[x],[y]，并將這8個方位傷的x和y坐標的增量預先放在一個結構數(shù)組move[8]中（見圖8）。該數(shù)組的每個分量有兩個域dx和dy。例如 要向東走，只要在j值上加上dy，就可以得到下一步位置的[x],[y]值為[i],[j+dy]。于是搜索方向的變化只要令方向值dir從0增至7，便可以從move數(shù)組中得到從[i],[j]點出發(fā)搜索到的每一個相鄰點[x],[y]。 x=i+move[dir].dx y=j+move[dir].dy dx dy 圖7 方向位移圖 圖8向量差圖 為了防止重走原路，我們規(guī)定對已經走過的位置，將原值為0改為-1，這既可以區(qū)別該位置是否已經走到過，又可以與邊界值1相區(qū)別。當整個搜索過程結束后可以將所有的-1改回到0，從而恢復迷宮原樣。 這樣計算機走迷宮的方法是：采取一步一步試探的方法。每一步都從（E）開始，按順時針對8個方向進行探測，若某個方位上的maze[x],[y]=0，表示可以通行，則走一步；若maze[x],[y]=1，表示此方向不可通行須換方向再試。直至8個方向都試過，maze[x],[y]均為1，說明此步已無路可走，需退回一步，在上一步的下一個方向重新開始探測。為此需要設置一個棧，用來記錄所走過的位置和方向（i，j，dir）。 當退回一步時，就從棧中退出一個元素，以便在上一個位置的下一個方向上探測，如又找到一個行進方向，則把當前位置和新的方向重新進棧，并走到新的位置。如果探測到x=m，y=n，則已經到達迷宮的出口，可以停止檢測，輸出存在棧中的路徑；若在某一位置的8個方向上都堵塞，則退回一步，繼續(xù)探測，如果已經退到迷宮的入口（棧中無元素），則表示此迷宮無路徑可通行。 2系統(tǒng)算法（偽代碼描述）： (1)建立迷宮節(jié)點的結構類型stack[]。 (2)入迷宮圖形 0表示可以通 1表示不可以通。 用二維數(shù)組maze[m+2][n+2]進行存儲。 數(shù)組四周用1表示墻壁，其中入口點（1，1）與出口點（m，n）固定。 (3)函數(shù)path()對迷宮進行處理，從入口開始： While(!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)&&(maze[x][y]==-1))) { For(掃描八個可以走的方向) { If(找到一個可以走的方向) { 進入棧 標志在當前點可以找到一個可以走的方向 避免重復選擇maze[x][y]=-1 不再對當前節(jié)點掃描 } If(八個方向已經被全部掃描過，無可以通的路) { 標志當前節(jié)點沒有往前的路 后退一個節(jié)點搜索 } } If(找到了目的地) { 輸出路徑退出循環(huán) } } 未找到路徑 (4)輸出從入口點到出口點的一條路徑。 (5)輸出標有通路的迷宮圖。 3.算法流程圖： 開始 初始化迷宮，顯示迷宮 初始化方向位移數(shù)組 尋找迷宮中的一條出路 If maze[x][y]==0 設1，1為出口 該點數(shù)據(jù)入棧 T F While 棧不空且dir<7 do elseIf dir<7 dir++ T F 回退一步 出口或入口 dir>=7 或?？? 顯示通路 結束 圖9 算法流程圖 4.程序代碼： #define M2 12 /*M2*N2為實際使用迷宮數(shù)組的大小*/ #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 //定義方向位移數(shù)組的元素類型對于存儲坐標增量的方向位移數(shù)組move { int dx,dy;}; //////////////////////////////////////////////////////////////////////////////////////////////////// void inimaze(int maze[][N2])////初始化迷宮 { int i,j,num; for(i=0,j=0;i<=M+1;i++)//設置迷宮邊界 maze[i][j]=1; for(i=0,j=0;j<=N+1;j++) maze[i][j]=1; for(i=M+1,j=0;j<=N+1;j++) maze[i][j]=1; cout<<"原始迷宮為："<top=-1; } /*inistack*/ int push(sqstktp*s,elemtype x) { if(s->top==maxlen-1) return(false); else { s->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); } else { s->top--; return(s->stack[s->top+1]); //棧不空，返回棧頂元素 } } //pop //////////////////////////////////////////////////////////////////////////////////// void path(int maze[][N2],struct moved move[],sqstktp *s) //尋找迷宮中的一條通路 { int i,j,dir,x,y,f; elemtype elem; i=1;j=1;dir=0; maze[1][1]=-1; //設[1][1]為入口處 do { x=i+move[dir].dx;//球下一步可行的到達點的坐標 y=j+move[dir].dy; if(maze[x][y]==0) { elem.x=i;elem.y=j;elem.dir=dir; f=push(s,elem);//如果可行將數(shù)據(jù)入棧 if(f==false)//如果返回假，說明棧容量不足 cout<<"棧長不足"; i=x;j=y;dir=0;maze[x][y]=-1; } else if (dir < 7) dir++; else { elem=pop(s); //8個方向都不行，回退 if(elem.x!=NULL) { i=elem.x; j=elem.y; dir=elem.dir+1; } } }while(!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)&&(maze[x][y]==-1))); //循環(huán) if(s->top==-1)//若是入口，則無通路 cout<<"此迷宮不通"; else { elem.x=x; elem.y=y; elem.dir=dir;//將出口坐標入棧 f=push(s,elem); cout<<"迷宮通路是："<top) { cout<<"("<stack[i].x<<","<stack[i].y<<")";//顯示迷宮通路 if(i!=s->top) cout<<"-->"; if((i+1)%4==0) cout<top>-1) //根據(jù)棧中元素的坐標，將通路的各個點的值改為8 { elem=pop(s); i=elem.x;j=elem.y; maze[i][j]=8; } for(i=1;i<=M;i++) { for(j=1;j<=N;j++) { printf("%3d",maze[i][j]); //顯示已標記通路的迷宮 } cout< #define M 5 /*行數(shù)*/ #define N 7 /*列數(shù)*/ #define MaxSize 100 /*棧最多元素個數(shù)*/ int mg[M+1][N+1]={ /*一個迷宮,其四周要加上均為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; } Stack[MaxSize],Path[MaxSize]; /*定義棧和存放最短路徑的數(shù)組*/ int top=-1; /*棧指針*/ int count=1; /*路徑數(shù)計數(shù)*/ int minlen=MaxSize; /*最短路徑長度*/ void mgpath() /*路徑為:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /*進棧*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1;mg[1][1]=-1; /*初始結點進棧*/ while (top>-1) /*棧不空時循環(huán)*/ { i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; if (i==M-2 && j==N-2) /*找到了出口,輸出路徑*/ { printf("%4d: ",count++); for (k=0;k<=top;k++) { printf("(%d,%d) ",Stack[k].i,Stack[k].j); if ((k+1)%5==0) printf("\n\t"); /*輸出時每5個結點換一行*/ } printf("\n"); if (top+1 int mg[M+2][N+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,int yi,int xe,int ye) //求解路徑為:(xi,yi)->(xe,ye) { struct { int i; //當前方塊的行號 int j; //當前方塊的列號 int di; //di是下一可走方位的方位號 } st[MaxSize]; //定義棧 int top=-1; //初始化棧指針 int i,j,k,di,find; top++; //初始方塊進棧 st[top].i=xi;st[top].j=yi; st[top].di=-1;mg[1][1]=-1; while (top>-1) //棧不空時循環(huán) { i=st[top].i;j=st[top].j;di=st[top].di; //取棧頂方塊 if (i==xe && j==ye) //找到了出口,輸出路徑 { printf("迷宮路徑如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",st[k].i,st[k].j); if ((k+1)%5==0) //每輸出每5個方塊后換一行 printf("\n"); } printf("\n"); return(1); //找到一條路徑后返回1 } find=0; while (di<4 && find==0) //找下一個可走方塊 { di++; switch(di) { case 0:i=st[top].i-1;j=st[top].j;break; case 1:i=st[top].i;j=st[top].j+1;break; case 2:i=st[top].i+1;j=st[top].j;break; case 3:i=st[top].i,j=st[top].j-1;break; } if (mg[i][j]==0) find=1;//找到下一個可走相鄰方塊 } if (find==1) //找到了下一個可走方塊 { st[top].di=di; //修改原棧頂元素的di值 top++; //下一個可走方塊進棧 st[top].i=i;st[top].j=j;st[top].di=-1; mg[i][j]=-1; //避免重復走到該方塊 } else //沒有路徑可走,則退棧 { mg[st[top].i][st[top].j]=0;//讓該位置變?yōu)槠渌窂娇勺叻綁K top--; //將該方塊退棧 } } return(0); //表示沒有可走路徑,返回0 } void main() { mgpath(1,1,M,N); } .