本文概述
递归迷宫算法是回溯算法的最佳示例之一。递归迷宫算法是解决迷宫的一种可能的解决方案。
迷宫
迷宫是一个被墙壁包围的区域。在这两者之间, 我们有一条从起点到终点的路径。我们必须从起点开始, 然后从终点开始。
迷宫原理
如上所述, 在迷宫中, 我们必须从起点移动到终点。问题是选择路径。如果在终点之前发现任何死角, 则必须回溯并移动方向。遍历的方向是北, 东, 西和南。我们必须继续“前进和后退”, 直到到达终点为止。
考虑我们有一个二维迷宫单元[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（墙）。继续相同的过程, 直到到达终点。
