|
文章目录
一，问题描述二，数据组织三，设计算法四，完整代码
一，问题描述
给定一个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 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
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;
}
参考资料：李春葆《数据结构教程》（第五版）
|