栈的应用之迷宫求解（C语言附完整代码）

文章目录

• 一，问题描述
• 二，数据组织
• 三，设计算法
• 四，完整代码

一，问题描述

给定一个MXN的迷宫图，求一条从指定入口到出口的迷宫路径。假设一个迷宫图如图所示(这里M=8,N=8),其中的每个方块用空白表示通道，用蓝色阴影表示障碍物。一般情况下,所求迷宫路径是简单路径，即在求得的迷宫路径上不会重复出现同一方块。一个迷官图的迷宫路径可能有多条，这些迷宫路径有长有短，这里仅仅考虑用栈求一条从指定入口到出口的迷宫路径。（因此利用栈进行迷宫求解得到的不一定是最优解）

二，数据组织

为了表示迷宫，设置一个数组mg，其中每个元素表示一个方块的状态,为0时表示对应方块是通道，为1时表示对应方块是障碍物。为了算法方便，一般在迷宫的外围加一条围墙。

int mg[M+2][N+2]=//由于迷宫四周加上了一条围墙，所以mg数组的行数和列数均加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}};

定义一种新的数据类型Box，来表示当前方块的行号，列号和下一步可走相邻方块的方位号

typedef struct{int i;//当前方块的行号int j;//当前方块的列号int di;//di是下一可走相邻方位的方位号} Box;

在该算法中使用顺序栈进行存储，声明迷宫栈如下：

typedef struct{Box data[MaxSize];//存放方块int top;//栈顶指针} StType;//定义栈类型

三，设计算法

对于迷宫中的每个方块，有上，下，左，右四个方向的相邻方块，将第i行j列的方块的位置记为( i , j )，规定该方块上方的方块为方位0，并按顺时针方向递增为其他方位编号，在试探过程中，从方位0到方位3的方向查找下一个可走的相邻方块。

迷宫求解在求解时使用“穷举法”，即从入口出发，按方位从0到3试探相邻的方块，如果找到一个相邻可走方块，就继续走下去并记下所走的方位。如果某个方块没有可走的相邻方块，则返回到前一个方块，换下一个方位继续试探，直到所有可能的通路都试探完为止。

为了保证在任何位置上都能沿原路退回（称为回溯），需要保存从入口到当前位置的路径上走过的方块，由于回溯的过程是从当前位置退回到前一个方块，体现出后进先出的特点，所以采用栈来保存走过的方块。

若一个非出口方块 ( i , j )是可走的，将它进栈，每个刚刚进栈的方块：其方位di置为-1(表示尚未试探它的周围)，然后开始从方位0到方位3试探这个栈顶方块的四周，如果找到某个方位d的相邻方块(i1，j1）是可走的，则将栈顶方块(i,j）的方位di置为d，同时将方块（i1，j1)进栈，再继续从方块(i1，j1)做相同的操作。若方块(i1 , j1 )的四周没有一个方位是可走的，将它退栈。

算法中应保证试探的相邻可走方块不是已走路径上的方块。如方块( i , j )已进栈，在试探方块( i+1，j ）的相邻可走方块时又会试探到方块( i , j ）。也就是说，从方块( i , j )出发会试探方块 ( i+1 , j ） ,而从方块( i+1, j ) 出发又会试探方块( i , j ），这样可能会引起死循环，为此在一个方块进栈后将相应的mg数组元素值改为-1（变为不可走的相邻方块），当退栈时（表示该栈顶方块没有可走相邻方块），将其恢复为0。

试探过程动画演示：

四，完整代码

#include #include #define MaxSize 100#define M 8#define N 8int 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}};//迷宫栈基本运算typedef struct{int i;//当前方块的行号int j;//当前方块的列号int di;//di是下一可走相邻方位的方位号} 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)//进栈元素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;//定义栈stInitStack(st);//初始化栈顶指针e.i=xi; e.j=yi;e.di=-1;//设置e为入口Push(st,e);//方块e进栈mg[xi][yi]=-1;//入口的迷宫值置为-1避免重复走到该方块while (!StackEmpty(st))//栈不空时循环{GetTop(st,e);//取栈顶方块ei=e.i; j=e.j; di=e.di;if (i==xe && j==ye)//找到了出口,输出该路径{ printf("一条迷宫路径如下:\n");k=0;while (!StackEmpty(st)){Pop(st,e);//出栈方块epath[k++]=e;//将e添加到path数组中}while (k>=1){k--;printf("\t(%d,%d)",path[k].i,path[k].j);if ((k+2)%5==0)//每输出每5个方块后换一行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;//找到一个相邻可走方块，设置find我真}if (find)//找到了一个相邻可走方块(i1,j1){st->data[st->top].di=di;//修改原栈顶元素的di值e.i=i1; e.j=j1; e.di=-1;Push(st,e);//相邻可走方块e进栈mg[i1][j1]=-1;//(i1,j1)的迷宫值置为-1避免重复走到该方块}else//没有路径可走,则退栈{Pop(st,e);//将栈顶方块退栈mg[e.i][e.j]=0;//让退栈方块的位置变为其他路径可走方块}}DestroyStack(st);//销毁栈return false;//表示没有可走路径,返回false}int main(){mgpath(1,1,M,N);return 0;}

参考资料：李春葆《数据结构教程》（第五版）