一.实验要求

1.题目

          给定一个M*N的迷宫图，求一条从指定入口到出口的迷宫路径。假设一个迷宫的示意图如下（这里M=8,N=8），其中的每个方块用空白表示通道，用阴影表示障碍物。

 

2.补充

        一般情况下，所求迷官路径是简单路径，即在求得的迷宫路径 上不会重复出现同一方块。一个迷官图的迷官路径可能有多条，这些迷宫路径有长有短，这里仅仅考虑用栈求一条从指定入口到出口的迷宫路径。

二.思路分析

1.构建初始环境

为了表示迷宫，设置一个数组mg,其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块是障碍物(不可走)。为了算法方便，一般在迷宫的外围加一条围墙（已在题目图中画出）。

2. 计运算算法

       对于速官中的每个方块，有上、下、左、右4个方块相邻，第i行第j列的当前方块的位置记为(i，j)，规定上方方块为方位0。并按顺时针方向递增编号。在试探过程中，假设按从方位0到方位3的方向查找下一个可走的相邻方块。
       求迷宫问题就是在一个指定的迷宫中求出从人口到出口的一 条路径。在求解时采用“穷举法”，即从人口出发按方位0到方位3的次序试探相邻的方块，一且找到一个可走的相邻方块就继续走下去,并记下所走的方位；若某个方块没有相邻的可走方块，则沿原路退回到前一个方块,换下一个位再继续试探，直到所有可能的通路都试探完为止。
        为了保证在任何位置上都能沿原路退回(称为回溯)，需要保存从人口到当前位置的路径上走过的方块，由于回溯的过程是从当前位置退回到前一个方块，体现出后进先出的特点,所以采用栈来保存走过的方块。i
        若一个非出口方块(i,j)是可走的,将它进栈,每个刚刚进栈的方块,其方位di置为-1(表示尚未试探它的周围),然后开始从方位0到方位3试探这个栈顶方块的四周，如果找到某个方位d的相邻方块(i，j)是可走的，则将栈顶方块(i,j)的方位d,置为d，同时将方块(i，j)进栈,再继续从方块(i，j)做相同的操作。若方块(i，j)的四周没有一个方位是可走的，将它退栈，前一个方块(x，y)变成栈顶方块，再从方块(x,y)的下一个方位继续试探。

 三.各部分功能实现

1.定义初始结构体

  • 采用栈指针s（不同于栈顶指针top）方式创建和使用顺序栈。


#define MaxSize 100

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

/*数据结构体的方位号表示某个方块下一步行走的方向，如下：
 （i-1，j)方位0，上  (i,j+1)方位1，右；
 （i+1，j）方位2，下；(i,j-1)方位3，左。
  类似于时钟旋转，以顺时针方向旋转
 */

//顺序栈的结构定义
typedef struct
{
	Box data[MaxSize];         //存放栈中的数据元素
	int top;                   //栈顶伪指针，存放栈顶元素在data数组中的下标
}StType;

2.初始设置环境

  • 交代迷宫的基础构成与算法思路
/*    
    解决迷宫问题最重要的就是找到一条出去的路径。在这里求解时，采用穷举法，即从入口出发，按方位0到方位3的次序试探相邻的
方块，一旦找到一个可走的相邻方块就继续走下去，并几下所走的方位；若某个方块没有相邻的可走方块，则沿原路返回前一个方
块，换一个方位继续尝试，直到所有的通路都试探完为止。
    沿原路返回，相当于进栈后再退出去，此时栈顶指针刚好指向前一个方块，符合后进先出的特点，所以使用顺序栈来保存。
*/                                

const int m=8,n=8;          //这里定义的是8*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}
};
/*
  这里可以采用读取文件的方式读入数据，但是为了节省空间，这里还是直接输入。
  1表示为障碍物，0表示对于方块为通道。
  本来是8*8的迷宫，但是为了美观，这里在上下两边定义了一圈围墙，故有m+2和n+2。
*/


/*
  算法思路：一个方块是（i，j）可走的，将他进栈，每一个刚进栈的方块，其di置为-1表示还没有试探他的周围，然后从0到3探索这个方块的四周。
  如果找到某个方位可以走，改变di的值，将可走相邻方块进栈，随后进行相同操作。
 问题：如果某个方块已进栈，探索相邻位置时，很可能探索到原来的那个方块，进而来回死循环，为此可以将一个方块进站后其对应的mg数组
  元素的值改为-1，当出栈（表示该方块没有相邻方块）将气质回复为0.
*/

3.初始化栈

  • 创建一个空栈，由s指向它。
//初始化栈
void InitStack(StType *&s)
{
	s=(StType * )malloc(sizeof(StType));          //分配一个顺序栈空间，首地址存放在s中，即s是一个指向顺序栈首地址得到伪指针
	s->top=-1;                                     //栈为空时，栈顶指针设置为-1
}

4.进栈

  • 在栈不满的情况下先将栈顶指针增1，然后在该位置上插上元素e，并返回真；否则返回假。
//进栈
bool Push(StType *&s,Box e)
{
	/*元素e进栈*/
	if(s->top==MaxSize-1)                      //栈满，溢出报错
		return false;
	s->top++;                                 //栈顶指针+1
	s->data[s->top]=e;                        //元素e放在栈顶指针处
	return true;
}

5.出栈

  • 在栈不为空的情况下先将栈顶元素赋值给e，然后将栈顶指针减1，并返回真；否则返回假。
//出栈
bool Pop(StType *&s,Box &e)               //&表示引用型，如果输出元素作为参数引用则添加该符号
{
	if (s->top==-1)                       //栈为空，向下溢出报错
		return false;
	e=s->data[s->top];                    //取栈顶元素
	s->top--;                             //栈顶指针-1
	return true;
}

6.取栈顶元素

  • 在栈不为空的情况下，将栈顶元素赋值给e并返回真；否则返回假。
//取栈顶元素
bool GetTop(StType *&s,Box &e)
{
	/*与出栈不同，该算法是读取栈顶元素，用e来存放栈顶元素*/
	if (s->top==-1)                       //栈为空，向下溢出报错
		return false;
	e=s->data[s->top];                    //取栈顶元素
	return true;
}

7.基础操作

  • 包括销毁和判断空
//销毁栈
void DestroyStack(StType *&s)
{
	free(s);
}

//判断空
bool StackEmpty(StType *s)
{
	return (s->top==-1);
}

8.*求迷宫路径

  • 核心算法
//求迷宫路径
bool mgpath(int x1,int y1,int x2,int y2)          //求解路径为(x1,y1)到（x2,y2)
{
	Box path[MaxSize],e;                //定义一个方块的集合和个体
	int i,j,di,k,il,jl;
	StType *s;                         //定义栈s
	InitStack(s);                     //初始化栈
	e.i=x1;e.j=y1;e.di=-1;             //设置e为入口
	Push(s,e);                        //首先入口e进栈
	mg [x1][x2]=-1;                  //入口e进栈后，将e设置为-1.避免重复走到该方块
	while(!StackEmpty(s))
	{
		GetTop(s,e);               //取栈顶的方块
		i=e.i;j=e.j;di=e.di;
		if(i==x2 && j==y2)         //如果栈顶是出口，输出该路径即可
		{
			printf("一条迷宫路径如下：\n");
			k=0;                             //计数器，计算path数组的长度
			while(!StackEmpty(s))
			{
				Pop(s,e);                   //出栈方块e
				path[k++]=e;                //将e添加到path数组中
			}
			/*一般情况下，k的值即路径长度大于1，这里为了输出美观做一些格式调整*/
			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(s);                   //输出完路径后为了节省空间，这里将栈销毁
			return true;                       //输出一条迷宫路径后返回true代表这部分完好
		}
		bool find=false;
		while(di<4 && !find)                //恒为真，一直执行
		{
			di++;                          //di顺时针递增
			switch(di)                     //用switch语句来表示各个方位
			{
			case 0:il=i-1;jl=j;break;
			case 1:il=i;jl=j+1;break;
			case 2:il=i+1;jl=j;break;
			case 3:il=i;jl=j-1;break;
			}
			if(mg[il][jl]==0)                   //找到一个相邻可走方块，设置find为真
				find=true;
		}
		if(find)                               //找到相邻可走方块后进栈并进行下一步
		{
			s->data[s->top].di=di;            //修改栈顶元素di的值，表示要进栈的元素是栈顶元素哪个方位的方块
			e.i=il;e.j=jl;e.di=-1;            //把找到的相邻可走方块信息赋予一个结构体实例
			Push(s,e);                        //把该实例进栈
			mg[il][jl]=-1;                    //进站后，把(il,jl)迷宫值改为-1，避免重复走到该模块
		}
		else                                  //如果没有相邻可走方块，则退栈
		{
			Pop(s,e);                         //将栈顶方块退栈
			mg[e.i][e.j]=0;                   //退栈后，将其迷宫的值回复原样
		}
	}
	DestroyStack(s);                         //算法完成后，无论找到与否，都销毁栈节省空间
	return false;                            //如果没有执行上面代码表示没有可走路径，返回false
}

四.完整实验代码

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*该次实验完成课本93页迷宫问题的实验，实验的迷宫模型采用课本的示意图*/

#define MaxSize 100

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

/*数据结构体的方位号表示某个方块下一步行走的方向，如下：
 （i-1，j)方位0，上  (i,j+1)方位1，右；
 （i+1，j）方位2，下；(i,j-1)方位3，左。
  类似于时钟旋转，以顺时针方向旋转
 */

//顺序栈的结构定义
typedef struct
{
	Box data[MaxSize];         //存放栈中的数据元素
	int top;                   //栈顶伪指针，存放栈顶元素在data数组中的下标
}StType;

/*    
    解决迷宫问题最重要的就是找到一条出去的路径。在这里求解时，采用穷举法，即从入口出发，按方位0到方位3的次序试探相邻的
方块，一旦找到一个可走的相邻方块就继续走下去，并几下所走的方位；若某个方块没有相邻的可走方块，则沿原路返回前一个方
块，换一个方位继续尝试，直到所有的通路都试探完为止。
    沿原路返回，相当于进栈后再退出去，此时栈顶指针刚好指向前一个方块，符合后进先出的特点，所以使用顺序栈来保存。
*/                                

const int m=8,n=8;          //这里定义的是8*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}
};
/*
  这里可以采用读取文件的方式读入数据，但是为了节省空间，这里还是直接输入。
  1表示为障碍物，0表示对于方块为通道。
  本来是8*8的迷宫，但是为了美观，这里在上下两边定义了一圈围墙，故有m+2和n+2。
*/


/*
  算法思路：一个方块是（i，j）可走的，将他进栈，每一个刚进栈的方块，其di置为-1表示还没有试探他的周围，然后从0到3探索这个方块的四周。
  如果找到某个方位可以走，改变di的值，将可走相邻方块进栈，随后进行相同操作。
 问题：如果某个方块已进栈，探索相邻位置时，很可能探索到原来的那个方块，进而来回死循环，为此可以将一个方块进站后其对应的mg数组
  元素的值改为-1，当出栈（表示该方块没有相邻方块）将气质回复为0.
*/

//初始化栈
void InitStack(StType *&s)
{
	s=(StType * )malloc(sizeof(StType));          //分配一个顺序栈空间，首地址存放在s中，即s是一个指向顺序栈首地址得到伪指针
	s->top=-1;                                     //栈为空时，栈顶指针设置为-1
}

//进栈
bool Push(StType *&s,Box e)
{
	/*元素e进栈*/
	if(s->top==MaxSize-1)                      //栈满，溢出报错
		return false;
	s->top++;                                 //栈顶指针+1
	s->data[s->top]=e;                        //元素e放在栈顶指针处
	return true;
}

//出栈
bool Pop(StType *&s,Box &e)               //&表示引用型，如果输出元素作为参数引用则添加该符号
{
	if (s->top==-1)                       //栈为空，向下溢出报错
		return false;
	e=s->data[s->top];                    //取栈顶元素
	s->top--;                             //栈顶指针-1
	return true;
}

//取栈顶元素
bool GetTop(StType *&s,Box &e)
{
	/*与出栈不同，该算法是读取栈顶元素，用e来存放栈顶元素*/
	if (s->top==-1)                       //栈为空，向下溢出报错
		return false;
	e=s->data[s->top];                    //取栈顶元素
	return true;
}

//销毁栈
void DestroyStack(StType *&s)
{
	free(s);
}

//判断空
bool StackEmpty(StType *s)
{
	return (s->top==-1);
}

//求迷宫路径
bool mgpath(int x1,int y1,int x2,int y2)          //求解路径为(x1,y1)到（x2,y2)
{
	Box path[MaxSize],e;                //定义一个方块的集合和个体
	int i,j,di,k,il,jl;
	StType *s;                         //定义栈s
	InitStack(s);                     //初始化栈
	e.i=x1;e.j=y1;e.di=-1;             //设置e为入口
	Push(s,e);                        //首先入口e进栈
	mg [x1][x2]=-1;                  //入口e进栈后，将e设置为-1.避免重复走到该方块
	while(!StackEmpty(s))
	{
		GetTop(s,e);               //取栈顶的方块
		i=e.i;j=e.j;di=e.di;
		if(i==x2 && j==y2)         //如果栈顶是出口，输出该路径即可
		{
			printf("一条迷宫路径如下：\n");
			k=0;                             //计数器，计算path数组的长度
			while(!StackEmpty(s))
			{
				Pop(s,e);                   //出栈方块e
				path[k++]=e;                //将e添加到path数组中
			}
			/*一般情况下，k的值即路径长度大于1，这里为了输出美观做一些格式调整*/
			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(s);                   //输出完路径后为了节省空间，这里将栈销毁
			return true;                       //输出一条迷宫路径后返回true代表这部分完好
		}
		bool find=false;
		while(di<4 && !find)                //恒为真，一直执行
		{
			di++;                          //di顺时针递增
			switch(di)                     //用switch语句来表示各个方位
			{
			case 0:il=i-1;jl=j;break;
			case 1:il=i;jl=j+1;break;
			case 2:il=i+1;jl=j;break;
			case 3:il=i;jl=j-1;break;
			}
			if(mg[il][jl]==0)                   //找到一个相邻可走方块，设置find为真
				find=true;
		}
		if(find)                               //找到相邻可走方块后进栈并进行下一步
		{
			s->data[s->top].di=di;            //修改栈顶元素di的值，表示要进栈的元素是栈顶元素哪个方位的方块
			e.i=il;e.j=jl;e.di=-1;            //把找到的相邻可走方块信息赋予一个结构体实例
			Push(s,e);                        //把该实例进栈
			mg[il][jl]=-1;                    //进站后，把(il,jl)迷宫值改为-1，避免重复走到该模块
		}
		else                                  //如果没有相邻可走方块，则退栈
		{
			Pop(s,e);                         //将栈顶方块退栈
			mg[e.i][e.j]=0;                   //退栈后，将其迷宫的值回复原样
		}
	}
	DestroyStack(s);                         //算法完成后，无论找到与否，都销毁栈节省空间
	return false;                            //如果没有执行上面代码表示没有可走路径，返回false
}

//主函数
int main()
{
	if(!mgpath(1,1,m,n))
		printf("该迷宫没有解！！！");
	return 1;
}

五.运行结果

 六.实验补充

这一次主要是使用数据结构中栈的相关操作，在此基础上，独立写出求解迷宫路径的算法。

同时数据结构还有线性表等，可以观看我的其他博客了解，同时下一篇博客还会用栈的链式存储结构完成。

线性表（链式存储）

线性表（顺序存储）

# 算法 # 数据结构 # c语言
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

“源”聚天大，码动未来|开放原子校源行（天津大学站）即将启幕！

11月22日，开放原子校源行（天津大学站）将在天津大学北洋园校区隆重举办。

avatar 开放原子开发者工作坊

openEuler系累计装机量突破1000万，树立操作系统产业新里程碑

11月15日，以“以智能，致世界”为主题的操作系统大会2024在北京中关村国际创新中心召开。

avatar 开放原子开发者工作坊

多模态大模型&科学计算双管齐下，百度飞桨两大赛项报名倒计时！

第二届开放原子大赛是由开放原子开源基金会组织举办的开源技术领域专业赛事，聚焦解决真问题，重点覆盖基础软件、工业软件、人工智能大模型等领域

avatar 开放原子开发者工作坊