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

Question

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

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

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

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

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

Answer 1

首先是作为通用概念的逻辑:您从左上角开始，为单元格指定 0。现在，对于与该单元格相邻的所有有效单元格，给它一个 1。继续向前移动，始终在所有方向上，将单元格增加 1。当您位于右下角时，您就有了最短路线!

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

生成迷宫必须有点随机，但同时它应该满足路径长度的要求。如果我们想将一个从 bottow-right 移开以生成路径长度，我们需要至少 1+2 个相同的向前移动(right-down-down 或 down-right-right)。如果我们想把2移走，我们需要2+2等等。

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