ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构之栈的应用----迷宫求解

fengxiaoke_fxk 分享于

2020腾讯云10周年活动,优惠非常大!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1040

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

推荐:数据结构:栈应用_求解迷宫问题3

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                          

/***********程序设计思想*************/ (1)迷宫地图相关: 利用动态二维数组来初步勾勒出迷宫: 建议先用malloc申请一维数组,再用calloc申请每个元素中的一维数组,因为我用的是1来表示迷宫的通路,0表示死路,calloc申请完后就会自动初始化为0 迷宫交岔路结点: 我们要有一个扫描通路的函数,对一个坐标进行东南西北的扫描,当遇到交岔路的坐标时,需要将所有的通路存入一个数组,扫描从东开始,至北结束,逆时针方向 这里设计的是单通道迷宫,也就是说不会有并行的通路,扫描出来的通路是不会超过两个的(肯定是不允许把结点来的那个原始方向认为是通路的) 当我们按着第一个方向走到死路时,我们需要返回到最近的一个交岔路结点,这之后第一个最重要的操作便是:将已确定的死路给封死,即把那个坐标的值从1改为0。 (2)栈相关: 栈在这里需要两个,一个存放走过的路径,也就是移动到一个坐标,就把这个坐标入栈,另一个是存放交岔路结点的,当我们遇到死路之后,就需要从交岔路结点栈中 弹出一个元素A,然后从所有路径的栈中一直弹出元素(就是原路返回),直到栈顶元素B与A相等,就表明已经退回到了最近的一个交岔路口 下一步便是走向另一个通路,直到遇到死路或终点 (3)设计根本: 整个程序是建立在递归应用中的,抽象出来就是:当我们规定一个优先方向(默认为东方向吧)、再规定一个固定的旋转方向(默认为逆时针)之后,我们会有一个从东方、 沿逆时针、到北方的总体走向,遇到一个死胡同,我们就要沿着路径原路返回,直到遇到一个十字路口,再走向另一个可通的方向,要是还是死胡同,就返回到再前一个十字 路口,进入另一个可通的方向,如此反复的探索,知道走到终点。 /***********程序设计细节*************/ (1)扫描通道函数----int Scan_Direction(data_type elem,int *all_direction,int **labyrinth); 返回值:返回所有可通方向的数量,可能值为0,1,2 重要参数:all_direction:记录所有可通的方向 关键实现: if(labyrinth[elem.x][elem.y+1] == YES && elem.direction != EAST){

direction = EAST;

all_direction[i++] = EAST;}坐标是按照二维数组的行列来规定的,这里给出的是判断当前坐标的东向是可通,YES表明可通,当坐标的东邻坐标([elem.x][elem.y+1])值为YES的时候,我们并不能 确定它的东方向就是可通的,因为有一种例外:当这个坐标就是从它的东邻坐标移过来的时候,这个坐标当然是可通的,所以在if的判断语句中还应加上一个判断语句: elem.direction != EAST,只有当这两个条件同时满足的时候才表明东邻为通,其余三个方向的判断与之类似 (2)根据方向的数目来走迷宫 case 1:先看只有一个方向可走到时候 这种情况很好解决,按着扫描的方向走一步就OK,让移动后的坐标入栈即可,这里我遇到了一个小问题,就是由于很多次的往回走,每一次都要入栈或出栈,貌似这样可能 造成路径栈中存在几个相同的坐标,并且这些坐标在栈中都是相邻的,所以我在每次入栈的时候都判断了一下,如果和栈顶元素相同,就不入栈了,以免最后弹出正确路径的 时候出现多个重复的坐标 case 2:这个条件是程序的关键部分,总的来说就是先走一个方向,若未遇到终点,就返回到交岔路结点,再走向另一条路,反复直到走到终点 case 2:{

Push_Stack(&cross_point,position);

GetElem_Stack(&path,&top_path);

if(top_path.x != pos

推荐:数据结构(迷宫求解c++)

#include "sqstack.h"Status InitStack(Stack &S){

S.top = 0 ;

for( int i = 0 ; i < MaxSize ; i++ )

{

S.data[i].di = 0 ;

S.data[i]

ition.x || top_path.y != position.y)

Push_Stack(&path,position);

Print_Position(position);

Move_Path(&position,all_direction[0],&path,&cross_point,labyrinth);

if(position.x == (LINE-2) && position.y == (ROW-2))

break;

Move_Path(&position,all_direction[1],&path,&cross_point,labyrinth);}break;首先让交岔路结点入栈(交叉点栈),让这个点入路径栈 接下来就是走向第一个方向,进入这个方向后,position将先通过all_direction[0]方向移动一格,然后利用递归,对新坐标进行扫描,判断出可通方向个数(0,1,2三种), 接着就开始重复昨天的故事,也就是递归了,当这一个方向走完后,这个Move_Path就结束了,然后判断是否到了终点,如果不是终点就进入第二个Move_Path,继续递归, 知道走到终点 这种递归过程,完全可以利用二叉树的图形来理解,先走完一个方向,再走另一个方向,二叉树如图: 箭头代表单通道,X代表死路 路线; 起点-->1-->3-->(弹出3)1-->4-->(弹出4、1)-->起点.... 这是左方向的走法,右方向按着这个方法走下去就能找到终点。 case 0: 当我们到了交叉点3的时候,会发现它是一个死胡同,即可通方向为0,这个时候就需要不断的弹出路径栈的元素,一直到交叉点1,进入交叉点4的方向。 (3)封掉已经确定的死路 当我们弹出交叉点1,返回到起点时,我们就可以确定从交叉点1走到方向的所有路都不可能走到终点,这个时候,我们就可以封掉交叉点1,即 把此坐标的值从1变为0 其实进行第二次Move_Path的时候,坐标已经到了交叉点2了,也就是说在交叉点2处扫描的时候,是不会检测交叉点1的,这样看来封掉死路似乎 没有必要,确实是的,但是如果你设计的Move_Path没有一进入就将坐标移到下一个位置的话,这个东西就必要了,也就是你再次在起点扫描可能 会又把交叉点1扫描进去,就造成了一个无限的函数嵌套了。。。 封掉死路只是一个我们思考的一个常识,根据个人而定。 (4)走迷宫循环的第一步(关键): if(count_direction != 0){

count_direction = Scan_Direction(position,all_direction,labyrinth);}else{

break;}这个代码应该算得上短小精悍,if条件语句表示在上一次循环中不是在case 0的switch语句中结束的,因为case 0本身就表示扫描的方向为0,如果这里没有这个判断, 那么满足下面两个条件的时候,程序就会出现问题: 1、上一次循环就是在case 0中结束的; 2、上一次循环存在于case 2中的第一个Move_Path中,而本次循环刚好又要求进入第二个Move_Path 即是:起始坐标是一个交叉点,all_direction本身就已经保存了两个方向,当你按第一个方向走到死路(case 0),你的position重新返回到了交叉点,这个时候你本该 退出这个函数,用all_direction中的第二个方向走下去,但是你却不可能退出while循环,因为你的position依旧要进行扫描,并且结果同样进入case 0,这样就会陷入死 循环,我们就需要加上这个if-else语句,当count_direction等于0时,就表明是从case 0中来的,就应该break,进入第二个函数

推荐:数据结构:栈应用_求解迷宫问题2

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                          

/***********程序设计思想*************/ (1)迷宫地图相关: 利用动态二维数组来初步勾勒出迷宫: 建议先用malloc申请一维数组,再用calloc申请每个元素中的一维数组,因为我用的是1来表示迷

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。