栈的应用之迷宫求解(C语言附完整代码)

这篇具有很好参考价值的文章主要介绍了栈的应用之迷宫求解(C语言附完整代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一,问题描述

给定一个MXN的迷宫图,求一条从指定入口到出口的迷宫路径。假设一个迷宫图如图所示(这里M=8,N=8),其中的每个方块用空白表示通道,用蓝色阴影表示障碍物。一般情况下,所求迷宫路径是简单路径,即在求得的迷宫路径上不会重复出现同一方块。一个迷官图的迷宫路径可能有多条,这些迷宫路径有长有短,这里仅仅考虑用栈求一条从指定入口到出口的迷宫路径。(因此利用栈进行迷宫求解得到的不一定是最优解
栈的应用之迷宫求解(C语言附完整代码)

二,数据组织

为了表示迷宫,设置一个数组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的方向查找下一个可走的相邻方块。
栈的应用之迷宫求解(C语言附完整代码)
迷宫求解在求解时使用“穷举法”,即从入口出发,按方位从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

试探过程动画演示:
栈的应用之迷宫求解(C语言附完整代码)

四,完整代码

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

参考资料:李春葆《数据结构教程》(第五版)文章来源地址https://www.toymoban.com/news/detail-464199.html

到了这里,关于栈的应用之迷宫求解(C语言附完整代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • DFS求解迷宫问题

       下面来具体分析一下算法的具体实现 首先要进行搜索,对搜索方向的顺序规定为:右--下--左--上   按照搜索顺序从起点开始搜索,在搜索的过程中将已经搜索过的位置设为已访问,这样我们就可以得到如下图所示的一条路线。 在到达终点后要进行回溯,利用 回溯 找到其

    2024年02月11日
    浏览(43)
  • A*算法求解迷宫寻路问题实验

    一、实验目标: 熟悉和掌握A*算法实现迷宫寻路功能,要求掌握启发式函数的编写以及各类启发式函数效果的比较。 二、实验内容与完成情况: 寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。迷宫寻路问题是在以方

    2024年02月04日
    浏览(40)
  • A*算法求解迷宫问题(算法讲解与证明、python实现与可视化)

    目录 一、引入 二、具体细节 1、BFS(Breadth First Search) 2、Dijkstra(Uniform Cost Search) 3、启发式(Heuristic search) 4、A*算法 4.1 算法细节 4.2 A与A*算法 4.3 A*算法证明 4.4 算法过程 三、具体实现 1、实验要求 2、代码实现 四、源代码        当我开始学习该算法时,网上已经有了很

    2023年04月08日
    浏览(56)
  • 『初阶数据结构 • C语言』⑩ - 栈的概念与实现(附完整源码)

        栈存储数据的方式跟数组一样,都是将元素排成一行。只不过它还有以下 3 条约束。   ● 只能在末尾插入数据。   ● 只能读取末尾的数据。   ● 只能移除末尾的数据。 你可以将栈看成一叠碟子:你只能看到最顶端那只碟子的碟面,其他都看不到。另外,要加碟子只能

    2024年02月16日
    浏览(51)
  • 多目标应用:MOGWO求解环境经济负荷分配问题(IEEE-30bus)提供MATLAB代码

    MOGWO原理参考文献: S. Mirjalili, S. Saremi, S. M. Mirjalili, L. Coelho, Multi-objective grey wolf optimizer: A novel algorithm for multi-criterion optimization, Expert Systems with Applications, in press, DOI: http://dx.doi.org/10.1016/j.eswa.2015.10.039 文献:吴亮红. 多目标动态差分进化算法及其应用研究[D].湖南大学,2011. 随着

    2024年02月04日
    浏览(65)
  • 【路径规划】(1) Dijkstra 算法求解最短路,附python完整代码

    好久不见,我又回来了, 这段时间把路径规划的一系列算法整理一下 ,感兴趣的点个关注。今天介绍一下机器人路径规划算法中最基础的 Dijkstra 算法,文末有 python 完整代码,那我们开始吧。 1959 年,荷兰计算机科学家 ·EdsgerWybe·Dijkstra 发表了论文《 A note on two problems in c

    2023年04月08日
    浏览(48)
  • 【路径规划】(2) A* 算法求解最短路,附python完整代码

    大家好,今天和各位分享一下机器人路径规划中非常经典的 A* 算法,感兴趣的点个关注,文末有 python 代码,那我么开始吧。 A* 算法是 1968 年 P.E.Hart[1]等人所提出的 在全局地图环境中所有已知情形下求解最短路径问题的方法,由于其简洁高效,容易实施 等 优点 而受到人们

    2024年02月03日
    浏览(36)
  • 数据结构--迷宫求解

    文章目录 一、问题的描述 二、系统功能设计 三、各个代码部分 四、整体代码及其运行 五、总结 迷宫求解--C语言 在一个迷宫中,需要我们找到出去的道路,并且得到的路经是最短的。 迷宫设置如下:迷宫使用标记(0,1,2,3分别代表迷宫的墙壁,通道,入口和出口) 从开

    2024年02月15日
    浏览(40)
  • 【算法】(BFS/DFS)迷宫路径问题(C语言)

    题目 :现有一迷宫如下图所示,蓝色部分为墙壁,白色部分为通路,入口在左上角(1,1)处,出口在右下角(8,8)处,试找出一条路径以通过该迷宫(路径不能重叠)。 分析 : ① 使用二维数组来存储迷宫,墙用 1 表示,路用 0 表示,如下图所示: 为与题目中的入口坐标

    2024年02月07日
    浏览(84)
  • 星辰秘典:解开Python项目的神秘面纱——迷宫之星(迷宫探索与求解)

    ✨博主: 命运之光 🌸专栏: Python星辰秘典 🐳专栏: web开发(html css js) ❤️专栏: Java经典程序设计 ☀️博主的其他文章: 点击进入博主的主页 前言:你好,欢迎来到我的博客。我是一个热爱编程的人,特别喜欢用Python这门语言来创造一些有趣的图形项目。在这篇博客

    2024年02月11日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包