一,问题描述
给定一个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。
试探过程动画演示:
文章来源:https://www.toymoban.com/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}
};
//迷宫栈基本运算
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; //定义栈st
InitStack(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); //取栈顶方块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数组中
}
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;
}
参考资料:李春葆《数据结构教程》(第五版)文章来源地址https://www.toymoban.com/news/detail-464199.html
到了这里,关于栈的应用之迷宫求解(C语言附完整代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!