迷宫求解的思路很简单，即所谓的“穷举求解”，从入口出发，顺某一方向探索，若能走通，则继续往前走，否则沿着原路退回，换一个方向继续探索，直至所有可能的通路都探索到为止。
为了保证在任何位置上都能沿着原路返回，需要使用栈来保存从入口到当前位置的路径。
这里采用之前介绍的顺序栈作为容器存储路径。
具体实现：
/****************************************
使用栈进行迷宫求解
by Rowandjj
2014/4/10
*****************************************/
#include<iostream>
using namespace std;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define TRUE 1
#define FALSE 0
//------------------迷宫求解----------------------------------
typedef struct _POSTYPE_//坐标类型
{
int x;//行
int y;//列
}PosType;
#define MAXLENGTH 25
typedef int MazeType[MAXLENGTH][MAXLENGTH];
MazeType m;//迷宫数组
int curstep = 1;//当前足迹，初值为1
typedef struct _SELEMTYPE_//栈元素类型
{
int ord;//序号
PosType seat;//当前坐标
int di;//下一方向(0-3分别代表东南西北)
}SElemType;
//-------------------栈定义------------------------------------
typedef int Status;
typedef struct _STACK_//栈的顺序存储结构
{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针，始终指在栈顶下一个元素
int stacksize;//栈容量
}SqStack;
/*栈操作定义*/
Status InitStack(SqStack *S);
Status DestroyStack(SqStack *S);
Status ClearStack(SqStack *S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status Pop(SqStack *S,SElemType *e);
Status StackTraverse(SqStack S,Status(*visit)(SElemType));
Status visit(SElemType e);
/*栈实现*/
Status InitStack(SqStack *S)
{
(*S).base = (SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
if(!(*S).base)
{
exit(OVERFLOW);
}
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S)
{
free((*S).base);
(*S).base = (*S).top = NULL;
(*S).stacksize = 0;
return OK;
}
Status ClearStack(SqStack *S)
{
(*S).top = (*S).base;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top == S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
Status GetTop(SqStack S,SElemType *e)
{
*e = *(--S.top);
return OK;
}
Status Push(SqStack *S,SElemType e)
{
if((*S).top - (*S).base >= STACK_INIT_SIZE)
{
(*S).base = (SElemType *)realloc((*S).base,(STACK_INIT_SIZE + STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
{
exit(OVERFLOW);
}
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++ = e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
{
return ERROR;
}
*e = *--(*S).top;
return OK;
}
Status StackTraverse(SqStack S,Status(*vi)(SElemType))
{
while(S.top>S.base)
{
vi(*S.base++);
}
cout<<endl;
return OK;
}
Status visit(SElemType e)
{
cout<<"("<<e.seat.x<<","<<e.seat.y<<")"<<" ";
return OK;
}
//---------------迷宫求解算法-------------------------
//定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹
Status Pass(PosType b)//判断当前路径是否可以通过
{
if(m[b.x][b.y] == 1)
{
return OK;
}
else
{
return ERROR;
}
}
void FootPrint(PosType a)//使迷宫m的a点的序号变为足迹(curstep)
{
m[a.x][a.y] = curstep;
}
PosType NextPos(PosType c,int di)//根据当前位置及移动方向，返回下一位置
{
PosType direc[4] = {{0,1},{1,0},{0,-1},{-1,0}};//行增量，列增量
c.x += direc[di].x;
c.y += direc[di].y;
return c;
}
void MarkPrint(PosType b)//使迷宫m的b点的序号变为-1(不能通过的路径)
{
m[b.x][b.y] = -1;
}
//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE
Status MazePath(PosType start,PosType end)
{
SqStack S;
PosType curpos;
SElemType e;
InitStack(&S);
curpos = start;
do
{
if(Pass(curpos))//当前位置可通
{
FootPrint(curpos);//留下足迹
e.ord = curstep;
e.seat.x = curpos.x;
e.seat.y = curpos.y;
e.di = 0;
Push(&S,e);//入栈当前位置及状态
curstep++;
if(curpos.x == end.x && curpos.y == end.y)//当前位置是出口
{
cout<<"路径如下"<<endl;
StackTraverse(S,visit);
return TRUE;
}
curpos = NextPos(curpos,e.di);//当前若不是出口则继续判断下一个位置
}else//当前位置不可通
{
if(!StackEmpty(S))
{
Pop(&S,&e);//当前位置出栈
curstep--;
while(e.di == 3 && !StackEmpty(S))//前一位置处于最后一个方向(北)
{
MarkPrint(e.seat);
Pop(&S,&e);
curstep--;
}
if(e.di < 3)//还有其他方向没有探索
{
e.di++;//换下一个方向探索
Push(&S,e);//改变方向后重新入栈
curstep++;
curpos = NextPos(e.seat,e.di);
}
}
}
} while (!StackEmpty(S));
return FALSE;
}
测试：
//--------------------测试------------------------------------
void Print(int x,int y)
{ /* 打印迷宫 */
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
printf("%3d",m[i][j]);
printf("\n");
}
}
int main()
{
PosType begin,end;
int i,j,x,y,x1,y1;
cout<<"请输入迷宫的行数,列数(包括外墙)：";
cin>>x;
cin>>y;
for(i=0;i<x;i++) /* 定义周边值为0(同墙) */
{
m[0][i]=0; /* 行周边 */
m[x-1][i]=0;
}
for(j=1;j<y-1;j++)
{
m[j][0]=0; /* 列周边 */
m[j][y-1]=0;
}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
m[i][j]=1; /* 定义通道初值为1 */
cout<<"请输入迷宫内墙单元数：";
cin>>j;
cout<<"请依次输入迷宫内墙每个单元的行数,列数：\n";
for(i=1;i<=j;i++)
{
cin>>x1;
cin>>y1;
m[x1][y1]=0; /* 定义墙的值为0 */
}
cout<<"迷宫结构如下:\n";
Print(x,y);
cout<<"请输入起点的行数,列数：";
cin>>begin.x;
cin>>begin.y;
cout<<"请输入终点的行数,列数：";
cin>>end.x;
cin>>end.y;
if(MazePath(begin,end)) /* 求得一条通路 */
{
cout<<"此迷宫从入口到出口的一条路径如下:\n";
Print(x,y); /* 输出此通路 */
}
else
printf("此迷宫没有从入口到出口的路径\n");
return 0;
}
运行结果：
解：
栈中保存的路径：
这里还可以使用递归来求出所有的解：
实现方式：
#include<IOSTREAM>
using namespace std;
typedef struct _POSTYPE_
{
int x;//行值
int y;//列值
}PosType;
#define MAXLENGTH 25
typedef int MazeType[MAXLENGTH][MAXLENGTH];//迷宫类型
PosType end;//终点
MazeType m;//迷宫
int x,y;//迷宫行数，列数
/* 定义墙元素值为0,可通过路径为-1,通过路径为足迹 */
void Print(int x,int y)
{ /* 输出解 */
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
printf("%3d",m[i][j]);
printf("\n");
}
printf("\n");
}
void Try(PosType cur,int curstep)//试探
{
int i;
PosType next;//下一位置
PosType direc[4] = {{0,1},{1,0},{0,-1},{-1,0}};//依次为东南西北
for(i = 0 ; i <= 3; i++)
{
next.x = cur.x+direc[i].x;
next.y = cur.y+direc[i].y;
if(m[next.x][next.y] == -1)//是通路
{
m[next.x][next.y] = ++curstep;
if(next.x != end.x || next.y != end.y)//若不是终点继续递归调用
{
Try(next,curstep);
}
else
{
system("pause");
Print(x,y);//输出结果
}
m[next.x][next.y] = -1;//恢复为通路，试探下一条路
curstep--;
}
}
}
int main()
{
PosType begin;
int i,j,x1,y1;
printf("请输入迷宫的行数,列数(包括外墙)：");
cin>>x;
cin>>y;
for(i=0;i<x;i++) /* 定义周边值为0(同墙) */
{
m[0][i]=0; /* 行周边 */
m[x-1][i]=0;
}
for(j=1;j<y-1;j++)
{
m[j][0]=0; /* 列周边 */
m[j][y-1]=0;
}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
m[i][j]=-1; /* 定义通道初值为-1 */
printf("请输入迷宫内墙单元数：");
cin>>j;
if(j)
printf("请依次输入迷宫内墙每个单元的行数,列数：\n");
for(i=1;i<=j;i++)
{
cin>>x1;
cin>>y1;
m[x1][y1]=0;
}
printf("迷宫结构如下:\n");
Print(x,y);
printf("请输入起点的行数,列数：");
cin>>begin.x;
cin>>begin.y;
printf("请输入终点的行数,列数：");
cin>>end.x;
cin>>end.y;
m[begin.x][begin.y]=1;
Try(begin,1); /* 由第一步起点试探起 */
return 0;
}