一，問題描述
給定一個(gè)MXN的迷宮圖，求一條從指定入口到出口的迷宮路徑。假設(shè)一個(gè)迷宮圖如圖所示(這里M=8,N=8),其中的每個(gè)方塊用空白表示通道，用藍(lán)色陰影表示障礙物。一般情況下,所求迷宮路徑是簡(jiǎn)單路徑，即在求得的迷宮路徑上不會(huì)重復(fù)出現(xiàn)同一方塊。一個(gè)迷官圖的迷宮路徑可能有多條，這些迷宮路徑有長有短，這里僅僅考慮用棧求一條從指定入口到出口的迷宮路徑。（因此利用棧進(jìn)行迷宮求解得到的不一定是最優(yōu)解）
二，數(shù)據(jù)組織
為了表示迷宮，設(shè)置一個(gè)數(shù)組mg，其中每個(gè)元素表示一個(gè)方塊的狀態(tài),為0時(shí)表示對(duì)應(yīng)方塊是通道，為1時(shí)表示對(duì)應(yīng)方塊是障礙物。為了算法方便，一般在迷宮的外圍加一條圍墻。
int mg[M+2][N+2]= //由于迷宮四周加上了一條圍墻，所以mg數(shù)組的行數(shù)和列數(shù)均加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}
};
定義一種新的數(shù)據(jù)類型Box，來表示當(dāng)前方塊的行號(hào)，列號(hào)和下一步可走相鄰方塊的方位號(hào)
typedef struct
{
int i; //當(dāng)前方塊的行號(hào)
int j; //當(dāng)前方塊的列號(hào)
int di; //di是下一可走相鄰方位的方位號(hào)
} Box;
在該算法中使用順序棧進(jìn)行存儲(chǔ)，聲明迷宮棧如下：
typedef struct
{
Box data[MaxSize]; //存放方塊
int top; //棧頂指針
} StType; //定義棧類型
三，設(shè)計(jì)算法
對(duì)于迷宮中的每個(gè)方塊，有上，下，左，右四個(gè)方向的相鄰方塊，將第i行j列的方塊的位置記為( i , j )，規(guī)定該方塊上方的方塊為方位0，并按順時(shí)針方向遞增為其他方位編號(hào)，在試探過程中，從方位0到方位3的方向查找下一個(gè)可走的相鄰方塊。
迷宮求解在求解時(shí)使用“窮舉法”，即從入口出發(fā)，按方位從0到3試探相鄰的方塊，如果找到一個(gè)相鄰可走方塊，就繼續(xù)走下去并記下所走的方位。如果某個(gè)方塊沒有可走的相鄰方塊，則返回到前一個(gè)方塊，換下一個(gè)方位繼續(xù)試探，直到所有可能的通路都試探完為止。
為了保證在任何位置上都能沿原路退回（稱為回溯），需要保存從入口到當(dāng)前位置的路徑上走過的方塊，由于回溯的過程是從當(dāng)前位置退回到前一個(gè)方塊，體現(xiàn)出后進(jìn)先出的特點(diǎn)，所以采用棧來保存走過的方塊。
若一個(gè)非出口方塊 ( i , j )是可走的，將它進(jìn)棧，每個(gè)剛剛進(jìn)棧的方塊：其方位di置為-1(表示尚未試探它的周圍)，然后開始從方位0到方位3試探這個(gè)棧頂方塊的四周，如果找到某個(gè)方位d的相鄰方塊(i1，j1）是可走的，則將棧頂方塊(i,j）的方位di置為d，同時(shí)將方塊（i1，j1)進(jìn)棧，再繼續(xù)從方塊(i1，j1)做相同的操作。若方塊(i1 , j1 )的四周沒有一個(gè)方位是可走的，將它退棧。
算法中應(yīng)保證試探的相鄰可走方塊不是已走路徑上的方塊。如方塊( i , j )已進(jìn)棧，在試探方塊( i+1，j ）的相鄰可走方塊時(shí)又會(huì)試探到方塊( i , j ）。也就是說，從方塊( i , j )出發(fā)會(huì)試探方塊 ( i+1 , j ） ,而從方塊( i+1, j ) 出發(fā)又會(huì)試探方塊( i , j ），這樣可能會(huì)引起死循環(huán)，為此在一個(gè)方塊進(jìn)棧后將相應(yīng)的mg數(shù)組元素值改為-1（變?yōu)椴豢勺叩南噜彿綁K），當(dāng)退棧時(shí)（表示該棧頂方塊沒有可走相鄰方塊），將其恢復(fù)為0。
試探過程動(dòng)畫演示：
文章來源：http://www.zghlxwxcb.cn/news/detail-464199.html
四，完整代碼
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
#define M 8
#define N 8
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}
};
//迷宮棧基本運(yùn)算
typedef struct
{
int i; //當(dāng)前方塊的行號(hào)
int j; //當(dāng)前方塊的列號(hào)
int di; //di是下一可走相鄰方位的方位號(hào)
} Box;
typedef struct
{
Box data[MaxSize]; //存放方塊
int top; //棧頂指針
} StType; //定義棧類型
void InitStack(StType *&s) //初始化棧
{ s=(StType *)malloc(sizeof(StType));
s->top=-1;
}
void DestroyStack(StType *&s) //銷毀棧
{
free(s);
}
bool StackEmpty(StType *s) //判斷棧是否為空
{
return(s->top==-1);
}
bool Push(StType *&s,Box e) //進(jìn)棧元素e
{
if (s->top==MaxSize-1)
return false;
s->top++;
s->data[s->top]=e;
return true;
}
bool Pop(StType *&s,Box &e) //出棧元素e
{
if (s->top==-1)
return false;
e=s->data[s->top];
s->top--;
return true;
}
bool GetTop(StType *s,Box &e) //取棧頂元素e
{
if (s->top==-1)
return false;
e=s->data[s->top];
return true;
}
//---------------------------------------------------------
bool mgpath(int xi,int yi,int xe,int ye) //求解路徑為:(xi,yi)->(xe,ye)
{
Box path[MaxSize], e;
int i,j,di,i1,j1,k;
bool find;
StType *st; //定義棧st
InitStack(st); //初始化棧頂指針
e.i=xi; e.j=yi; e.di=-1; //設(shè)置e為入口
Push(st,e); //方塊e進(jìn)棧
mg[xi][yi]=-1; //入口的迷宮值置為-1避免重復(fù)走到該方塊
while (!StackEmpty(st)) //棧不空時(shí)循環(huán)
{
GetTop(st,e); //取棧頂方塊e
i=e.i; j=e.j; di=e.di;
if (i==xe && j==ye) //找到了出口,輸出該路徑
{
printf("一條迷宮路徑如下:\n");
k=0;
while (!StackEmpty(st))
{
Pop(st,e); //出棧方塊e
path[k++]=e; //將e添加到path數(shù)組中
}
while (k>=1)
{
k--;
printf("\t(%d,%d)",path[k].i,path[k].j);
if ((k+2)%5==0) //每輸出每5個(gè)方塊后換一行
printf("\n");
}
printf("\n");
DestroyStack(st); //銷毀棧
return true; //輸出一條迷宮路徑后返回true
}
find=false;
while (di<4 && !find) //找相鄰可走方塊(i1,j1)
{
di++;
switch(di)
{
case 0:i1=i-1; j1=j; break;
case 1:i1=i; j1=j+1; break;
case 2:i1=i+1; j1=j; break;
case 3:i1=i; j1=j-1; break;
}
if (mg[i1][j1]==0) find=true; //找到一個(gè)相鄰可走方塊，設(shè)置find我真
}
if (find) //找到了一個(gè)相鄰可走方塊(i1,j1)
{
st->data[st->top].di=di; //修改原棧頂元素的di值
e.i=i1; e.j=j1; e.di=-1;
Push(st,e); //相鄰可走方塊e進(jìn)棧
mg[i1][j1]=-1; //(i1,j1)的迷宮值置為-1避免重復(fù)走到該方塊
}
else //沒有路徑可走,則退棧
{
Pop(st,e); //將棧頂方塊退棧
mg[e.i][e.j]=0; //讓退棧方塊的位置變?yōu)槠渌窂娇勺叻綁K
}
}
DestroyStack(st); //銷毀棧
return false; //表示沒有可走路徑,返回false
}
int main()
{
mgpath(1,1,M,N);
return 0;
}
參考資料：李春葆《數(shù)據(jù)結(jié)構(gòu)教程》（第五版）文章來源地址http://www.zghlxwxcb.cn/news/detail-464199.html
到了這里，關(guān)于棧的應(yīng)用之迷宮求解（C語言附完整代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
