数据结构论坛

首页 » 分类 » 分类 » 数据结构实验2使用栈的方法求解迷宫从
TUhjnbcbe - 2021/2/6 3:21:00
北京市中科医院好不好         https://m-mip.39.net/baidianfeng/mipso_5154118.html

题目:求解迷宫从入口到出口的路径。输入一个迷宫,求从入口通向出口的可行路径。为简化问题,迷宫用二维数组intmaze[10][10]来存储障碍物的分布,假设迷宫的横向和纵向尺寸的大小是一样的,并由程序运行读入,若读入迷宫大小的值是n(3n=10),则该迷宫横向或纵向尺寸都是n,规定迷宫最外面的一圈是障碍物,迷宫的入口是maze[1][1],出口是maze[n-2][n-2],若maze[j]=1代表该位置是障碍物,若maze[j]=0代表该位置是可以行走的空位(0=i=n-1,0=j=n-1)。求从入口maze[1][1]到出口maze[n-2][n-2]可以走通的路径。要求迷宫中只允许在水平或上下四个方向的空位上行走,走过的位置不能重复走,规定必须按向右、向下、向左、向上的顺序向前搜索试探。如下这样一个迷宫:

本题要求必须使用严格的搜索顺序,即从右,从下,从左,从上,并非要找到最短路径,例如上图我们得到的路径应该是:

所以应该得到程序结果为:

对于此题,数据结构老师要求使用栈的解法,一般首先想到的是动态规划,那栈的解法又该如何解决此问题呢?

首先参考到数据结构书关于这一部分的讲解:

作为一种不太好想到其实也并不优秀的解法,该如何去写这一题呢?

首先,进入一个位置,就将该位置压入栈中,该位置验证失败那就弹出该位置,如果成功完成,就修改标志,输出,结束。

优化:

①采用c++结构体定义Point,用于保存是否读写过,是否可以走,终点的信息。

②重载标准输出流,使得可以方便地输出(x,y)结构。

本题采用顺序栈,顺序栈代码在之前已有讲解,

1