C语言求解迷宫问题（顺序栈）

本文主要锻炼栈的相关操作，并使用完成迷宫求解问题。

终究还是散了

3293人浏览 · 2023-04-13 17:07:17

终究还是散了 · 2023-04-13 17:07:17 发布

一.实验要求

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;
}