這篇文章給大家分享的是有關(guān)C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中求解迷宮問(wèn)題的示例分析的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。
C語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)中求解迷宮問(wèn)題實(shí)現(xiàn)方法
首先求迷宮問(wèn)題通常用的是“窮舉求解” 即從入口出發(fā)，順某一方向試探，若能走通，則繼續(xù)往前走，否則原路返回，換另一個(gè)方向繼續(xù)試探，直至走出去。
我們可以先建立一個(gè)8*8的迷宮其中最外側(cè)為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對(duì)應(yīng)通道方塊，1代表墻。對(duì)于迷宮中的每個(gè)方塊，有上下左右4個(gè)方塊相鄰，我們規(guī)定第i行第j列方塊的位置為（i,j） 規(guī)定上方方塊方位為0，順時(shí)針?lè)较蜻f增編號(hào)。(i,j)上方的即為(i-1,j),下方(i+1,j)，左方(i,j-1)，右方(i,j+1). 為了方面回溯，我們需要有進(jìn)棧出棧操作，所以我們來(lái)定義：
struct {
int i;//當(dāng)前方位行
int j;//當(dāng)前方位列
int di;//下一個(gè)可走方位號(hào)
}St[MaxSize];//棧
int top=-1;//初始化棧頂指針我們來(lái)看看文字過(guò)程~~
首先將入口進(jìn)棧（初始方位為-1），在棧不空的情況下循環(huán)：取棧頂方塊（不退棧），若該方塊是出口，則退棧。若存在這樣的方塊，則將其方位保存到棧頂元素中，并將這個(gè)可走的相鄰方塊進(jìn)棧。
對(duì)應(yīng)的算法：
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個(gè)換一行
}
printf("\n"); //找到一條路徑后結(jié)束
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){ //找到了下一個(gè)可走方塊
St[top].di=di;//修改原棧頂?shù)闹? top++; //下一個(gè)可走方塊進(jìn)棧
St [top].i=i; St[top].j=j;St[top].di=-1;
mg[i] [j]=-1;//避免重復(fù)走到該方塊
}
else{ //沒(méi)有路徑可走,進(jìn)行退棧操作
mg[St[top].i] [St[top].j]=0;//讓該位置變?yōu)槠渌窂降目勺叻綁K
top--;
}
}
printf("沒(méi)有路徑可走!\n");
}當(dāng)然我們也可以用隊(duì)列去求該迷宮的最優(yōu)算法，這只是一個(gè)用來(lái)理解棧的例子~~~
感謝各位的閱讀！關(guān)于“C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中求解迷宮問(wèn)題的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
