algorithm - 生成具有指定长度路径的迷宫

Question

我的问题很简单，但很难做到。我有迷宫的大小和路径的长度。我需要找到完全指定长度的路径。然而，迷宫可以包含有效的更长路径。迷宫总是从 [0, 0] 开始并在 [size X, size Y] 结束。路径长度为 13 的 5x5 迷宫示例：（X：墙，-：路径）

---XX
XX-XX
---XX
-XXXX
-----

6x6 迷宫，11 条路径长度（包含另一条大小为 15 的路径）- 有效

------
XX-XX-
---XX-
-XXXX-
-XXXX-
------

我已经尝试了很多算法，但没有任何效果。如果有人能给我一些关于我需要做什么或者我可以在哪里阅读这个问题的提示，那就太好了。

标签： algorithm

Answer 1

首先将逻辑作为通用概念：您从左上角开始，给单元格一个 0。现在对于与该单元格相邻的所有有效单元格，给它一个 1。继续前进，总是在所有方向上，将单元格增加 1。当你在右下角时，你有最短的路线！

现在我们需要看看方向性影响。当我们离开右下角时，我们必须再次向前迈出一步来弥补这一点。因此最小步长为 12，每个较大的路径为 p + 2。在 15 的路径中，我们从右下角移动 2 步（第 5 步和第 6 步），因此路径长度 = 12 + 2*2 = 16。

生成迷宫必须有点随机，但同时它应该满足路径长度的请求。如果我们想从右下角移动一个以生成路径长度，我们需要在向前方向上至少有 1+2 次相同的移动（右下下或右下）。如果我们想将 2 移开，我们需要 2+2，以此类推。

如果你真的想随机，你需要使用回溯，你尝试每一种可能性并检查是否仍然可以完成步骤。让我们举个例子，我们想要 14 个步骤）：当我们放置 7 时，单元格 [2,3] 和 [4,3] 被阻塞。当我们放置 8 时，单元格 [2,4]、[2,5] 和 [3,5] 被阻塞。现在没有剩余空间可以向左或向上移动，因此不可能将 8 放在 [4,4] 上。8 可以放在 [2,4] 上。