递归迷宫算法

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

迷宫

迷宫是被墙壁包围的区域；在两者之间，我们有从起点到终点的路径。 我们必须从起点开始，然后从终点前进。

迷宫原理

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

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

现在从起始位置开始改变（因为边界已填充为 1），找到下一个空闲单元格，然后转向下一个空闲单元格，依此类推。 如果我们抓住一个死胡同，我们必须回溯并将路径中的单元格设为 1（墙）。 继续相同的过程，直到到达终点。