建宸教程网

标题: 方法递归的经典案例--简易迷宫问题 [打印本页]

作者: 密战    时间: 2021-1-1 10:30
标题: 方法递归的经典案例--简易迷宫问题
迷宫中的方法递归思想

问题引入( 如图简易迷宫,小球从arr【0】【0】进入,到arr【6】【6】出来)

如图,起点在arr【0】【0】终点是arr【6】【6】
我们从起点出发,到达终点,打印走过的路径222。

★如图,0体现我们门路没有走过的路(小球只能走0,因为2和3都被走过),2体现正确路径,3体现死路。
我们要想解决这个问题就要引入我们所说的方法递归,这是我们解决迷宫问题。
我们平日里走迷宫,也只有一种办法,去试!盘算机也是如此,因此我们要设计一个方法,让代码不停去实验每条路径,我们不妨这样设计—分4步,先让小球往下走,走不通就往右走,再不可往上走,再不可往左走。每一步都这样,我们将称其为一套利用,每一个0点我们都要举行这样一套利用。这样如果对于如下图(直来直去的迷宫)所示的迷宫是很好明白的。

但是,我们的迷宫通常都是有好几条死胡同的,我们设想,如果只有上面的方法,我们如果遇到了一条这样的
胡同

那么我们仅仅按照上面的走法,

当我们到达绿色框的时候,就需要往右走,发现不可,那就往上,可以,我们在对绿色框上面的位置举行一套利用,小球会先往下走。到这就不对劲了,那不是小球一直在这两个之间运动了吗!
没错,这个时候,我们就来讲一下解决问题的第二个关键,回溯思想,我们自己在走迷宫的时候,我们知道,如果这是一条死胡同,那么我们就要回到进入死胡同的地方,选择另一条路,盘算机也是如此,我们就要想办法回到死胡同入口处

让盘算机知道,向下走是走不通的,要在紫色框中向右走。这需要一个回溯思想,我们其实每走一步,就是调用了一次方法,再在方法中调用方法,层层叠加,小球必须走0,但是到达绿色框7的时候,发现四周除了墙就是走过的路(我们成这个点为死点,将其标记为3),那就回它的方法调用之处,也就是框6


计划的是回到框6之后,发现情况跟在7的时候一样,四周除了2就是墙,那就再回到调用出框5,一直这样下去,最后回到框2,执行第二步向右走,乐成解决死胡同问题
来源:https://blog.csdn.net/wokkkok/article/details/111880336
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!




欢迎光临 建宸教程网 (https://www.jianchenwangluo.com/) Powered by Discuz! X3.4