C語言 數據結構中求解迷宮問題實現方法
在學習數據結構棧的這一節遇到了求迷宮這個問題，拿來分享一下~
首先求迷宮問題通常用的是“窮舉求解” 即從入口出發，順某一方向試探，若能走通，則繼續往前走，否則原路返回，換另一個方向繼續試探，直至走出去。
我們可以先建立一個8*8的迷宮其中最外側為1的是墻
int mg[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1},}如上所示，0對應通道方塊，1代表墻。對于迷宮中的每個方塊，有上下左右4個方塊相鄰，我們規定第i行第j列方塊的位置為（i,j） 規定上方方塊方位為0，順時針方向遞增編號。(i,j)上方的即為(i-1,j),下方(i+1,j)，左方(i,j-1)，右方(i,j+1). 為了方面回溯，我們需要有進棧出棧操作，所以我們來定義：
struct { int i;//當前方位行 int j;//當前方位列 int di;//下一個可走方位號}St[MaxSize];//棧int top=-1;//初始化棧頂指針我們來看看文字過程~~
首先將入口進棧（初始方位為-1），在棧不空的情況下循環：取棧頂方塊（不退棧），若該方塊是出口，則退棧。若存在這樣的方塊，則將其方位保存到棧頂元素中，并將這個可走的相鄰方塊進棧。
對應的算法：
void mgpath(int x1,int y1,int x2,int y2){ int i.j,di,find,k; top++; St[top].i=x1; St[top].j=y1; St[top].di=-1; mg[x1][y1]=-1; while (top>-1){ i=St[top].i; j=St[top].j; di=St[top].di; if (i==x2 && j==y2){ printf("迷宮路徑如下：/n"); for (k=0;k<=top;k++){ printf("/t(%d,%d)",St[k].i,S[k].j); if ((k+1)%5==0) printf("/n"); //輸出5個換一行 } printf("/n"); //找到一條路徑后結束 return ; } find=0; while (di<4 && find==0){ di++; switch(di){ case 0: i=St[top].i-1; j=S[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;//修改原棧頂的值 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;//讓該位置變為其他路徑的可走方塊 top--; }} printf("沒有路徑可走!/n");}當然我們也可以用隊列去求該迷宮的最優算法，這只是一個用來理解棧的例子~~~
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
