递归迷宫算法

本文概述

递归迷宫算法是回溯算法的最佳示例之一。递归迷宫算法是解决迷宫的一种可能的解决方案。

迷宫

迷宫是一个被墙壁包围的区域。在这两者之间, 我们有一条从起点到终点的路径。我们必须从起点开始, 然后从终点开始。

递归迷宫算法

迷宫原理

如上所述, 在迷宫中, 我们必须从起点移动到终点。问题是选择路径。如果在终点之前发现任何死角, 则必须回溯并移动方向。遍历的方向是北, 东, 西和南。我们必须继续“前进和后退”, 直到到达终点为止。

考虑我们有一个二维迷宫单元[WIDTH] [HEIGHT]。在这里, 单元格[x] [y] = 1表示墙, 单元格[x] [y] = 0表示迷宫中特定位置x, y的自由单元格。我们可以在阵列中更改的方向是北, 东, 西和南。第一步是将二维数组的边界设为一个, 这样我们就不会走出迷宫而通常随时都驻留在迷宫中。

示例迷宫
1 1 1 1 1 1 1
1 0 0 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 0 0 1
1 1 1 1 1 0 1
1 1 1 1 1 1 1

现在从起始位置开始更改(因为边界被1填充), 找到下一个空闲单元格, 然后转到下一个空闲单元格, 依此类推。如果我们抓住死胡同, 就必须回溯并使路径中的像元成为1(墙)。继续相同的过程, 直到到达终点。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?