---

一，问题描述

给定一个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 <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;
}

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