文档章节

迷宫问题:顺序栈解法

LoSingSang
 LoSingSang
发布于 2018/10/20 17:58
字数 386
阅读 48
收藏 0

采用顺序栈以及回溯法,一个比较简单的问题,但是从来没有写过,也算是弥补一下自己欠数据结构的债吧,居然也花了一个半小时,无地自容了。。

定义好数据结构求解算法就显得容易一些了。

struct Box
{
	int i;
	int j;
	int di;
};
struct stType
{
	Box data[MaxSize];
	int top;
};

整体算法:

bool mgpath(int i, int j, int M, int N)
{
	stType st;
	st.top = 0;
	st.data[st.top].i = i;
	st.data[st.top].j = j;
	st.data[st.top].di = -1;
	mg[i][j] = -1;

	while (st.top > -1)
	{
		if (st.data[st.top].i == M && st.data[st.top].j == N )
		{
			std::cout << "迷宫路径为:" << std::endl;
			for (int k = 0; k < st.top; ++k)
			{
				std::cout << "(" << st.data[k].i << ", " << st.data[k].j << ") ";
				if ((k + 1) % 4 == 0)
				{
					std::cout << std::endl;
				}
			}
			std::cout << "(" << M << ", " << N << ") ";
			std::cout << std::endl;
			return true;
		}
		int find = 0;
		int di = st.data[st.top].di;
		++di;
		int ii, jj;
		while (0 == find && 4 > di)
		{
			switch (di)
			{
			case 0: ii = st.data[st.top].i - 1, jj = st.data[st.top].j; break;
			case 1:	ii = st.data[st.top].i, jj = st.data[st.top].j + 1; break;
			case 2:	ii = st.data[st.top].i + 1, jj = st.data[st.top].j; break;
			case 3:	ii = st.data[st.top].i, jj = st.data[st.top].j - 1; break;
			}

			if (mg[ii][jj] == 0)
			{
				find = 1;
			}
			else
			{
				++di;
			}

		}

		if (1 == find)
		{
			st.data[st.top].di = di;
			++st.top;
			st.data[st.top].i = ii;
			st.data[st.top].j = jj;
			st.data[st.top].di = -1;
			mg[ii][jj] = -1;
		}
		else
		{
			--st.top;
		}

	}

	return false;
}

 

完整代码:https://gitee.com/feistel/codes/06b241nc59uifelwprms756

© 著作权归作者所有

共有 人打赏支持
LoSingSang
粉丝 3
博文 51
码字总数 15947
作品 0
深圳
程序员
私信 提问
剑指Offer学习总结-从尾到头打印链表

剑指Offer学习总结-从尾到头打印链表 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000
2018/01/16
0
0
LeetCode算法题-Min Stack(Java实现)

这是悦乐书的第177次更新,第179篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第36题(顺位题号是155)。设计一个支持push,pop,top和在恒定时间内检索最小元素的堆栈。 pu...

小川94
2018/11/20
0
0
LeetCode算法题-Implement Stack Using Queues

这是悦乐书的第193次更新,第198篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第54题(顺位题号是225)。使用队列实现栈的以下操作: push(x) - 将元素x推入栈。 pop() ...

小川94
2018/12/06
0
0
LeetCode算法题-Binary Tree Level Order Traversal II(Java实现)

这是悦乐书的第165次更新,第167篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第24题(顺位题号是107)。给定二叉树,返回其节点值的自下而上级别顺序遍历(即从左到右,逐层...

小川94
2018/11/08
0
0
菜鸟的进击——C语言实现老鼠走迷宫

老鼠走迷宫,一只实验室的小老鼠被用来做迷宫智力实验。科学家在迷宫的一角放上一块奶酪,小老鼠要在最快时间内找到奶酪。 老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙...

柳猫
2018/06/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 白掌柜说了卖货不卖身

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @爱漫爱 :这是一场修行分享羽肿的单曲《Moony》 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :开不开心? 开心呀, 我又不爱睡懒觉…...

小小编辑
今天
15
3
大数据教程(11.7)hadoop2.9.1平台上仓库工具hive1.2.2搭建

上一篇文章介绍了hive2.3.4的搭建,然而这个版本已经不能稳定的支持mapreduce程序。本篇博主将分享hive1.2.2工具搭建全过程。先说明:本节就直接在上一节的hadoop环境中搭建了! 一、下载apa...

em_aaron
今天
5
0
开始看《JSP&Servlet学习笔记》

1:WEB应用简介。其中1.2.1对Web容器的工作流程写得不错 2:编写Servlet。搞清楚了Java的Web目录结构,以及Web.xml的一些配置作用。特别是讲了@WebServlet标签 3:请求与响应。更细致的讲了从...

max佩恩
今天
5
0
mysql分区功能详细介绍,以及实例

一,什么是数据库分区 前段时间写过一篇关于mysql分表的的文章,下面来说一下什么是数据库分区,以mysql为例。mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面(可...

吴伟祥
今天
5
0
SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部