文档章节

迷宫问题:顺序栈解法

LoSingSang
 LoSingSang
发布于 10/20 17:58
字数 386
阅读 25
收藏 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
博文 29
码字总数 5248
作品 0
深圳
程序员
私信 提问
剑指Offer学习总结-从尾到头打印链表

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

wwlcsdn000
01/16
0
0
LeetCode算法题-Binary Tree Level Order Traversal II(Java实现)

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

小川94
11/08
0
0
数据结构-迷宫问题(回溯法)

题目描述: 迷宫是一个二维矩阵,其中1为墙,0为路,入口在第一列,出口在最后一行。要求从入口开始,从出口结束,按照 上,下,左,右 的顺序来搜索路径.。 思路: 回溯法 + 试探法。回溯法可用栈或递...

sssssuuuuu666
2017/12/11
0
0
菜鸟的进击——C语言实现老鼠走迷宫

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

柳猫
06/01
0
0
「Python 算法实战」:栈

栈(stack)又称之为堆栈是一个特殊的有序表,其插入和删除操作都在栈顶进行操作,并且按照先进后出,后进先出的规则进行运作。 如下图所示 例如枪的弹匣,第一颗放进弹匣的子弹反而在发射出去...

大数据之路
2012/07/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊storm的ICommitterTridentSpout

序 本文主要研究一下storm的ICommitterTridentSpout ICommitterTridentSpout storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSpout.java public interface......

go4it
23分钟前
1
0
Ubuntu常用操作

查看端口号 netstat -anp |grep 端口号 查看已使用端口情况 netstat -nultp(此处不用加端口号) netstat -anp |grep 82查看82端口的使用情况 查找被占用的端口: netstat -tln netstat -tl...

hc321
昨天
1
0
网站cdn的静态资源突然访问变的缓慢,问题排查流程

1.首先我查看了一下是否自己的网络问题,通过对比其他资源的访问速度和下载速度,确认不是 2.通过ping 和 tracert 判断cdn域名能否正常访问,(最后回想感觉这一步可以省略,因为每次最终能访...

小海bug
昨天
3
0
Mybatis 学习笔记四 MyBatis-Plus插件

Mybatis 学习笔记四 MyBatis-Plus插件 maven依赖 <dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus</artifactId> <ve......

晨猫
昨天
5
0
小白带你认识netty(二)之netty服务端启动(下)

承接上一篇小白带你认识netty(二)之netty服务端启动(上),还剩下两步骤:3、注册Selector:将Channel注册到Selector上 和 4、端口的绑定:服务端端口的监听。 3、注册Selector:将Chann...

天空小小
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部