algorithm - 关于 Codility 的 HilbertMaze 任务

Question

任何人都可以提示我如何处理 Codility 的以下任务:https://codility.com/programmers/task/hilbert_maze/

我可以通过生成迷宫并使用 BFS 搜索最短路径来找到最短路径，但是由于最坏情况下的时间复杂度预计为 O(N) 我认为这不是正确的方法。 BFS 的时间复杂度为 O(|V| + |E])，其中 V 是顶点数，E 是边数。例如，如果 N = 3，我们有一个大小为 17x17 的网格，很明显我们不能仅用 3 步就找到路径。

因此，要么指示的时间复杂度是错误的，应该是 M^2 之类的东西，要么有一个快速技巧可以在不使用图形算法的情况下简单地计算两点之间的距离。我找到了一些算法来计算 2 个给定点的希尔伯特距离(如果这是这里需要的)，它们使用位操作等，但根本无法理解它们。此外，我认为该任务的目标是自行找出如何计算距离，而不是使用现有公式。

是否有人解决了这个任务并可以进一步帮助我？谢谢!

Answer 1

这是我想出的解决方案:

1. 每个点的位置都可以由一组象限及其方向(它将有 N 个元素)定义 - 每个元素代表前一个象限中的方向。整个迷宫朝上
2. 你需要为这两个点定义这个数组。例如:如果 N = 2 并且该点位于左下象限，那么它将具有向左的方向。我们采用这个象限并旋转我们的坐标系，使其方向相同。通过这种方式，我们在新系统中定义了下一个象限和方向对。因此，如果我们的点位于左下象限，那么它的方向将向左，但由于这是相对于我们之前的方向(也是向左)，这将变成向上的方向。
3. 此时，我们已经有了所有象限和方向，一直到包含我们点的最小迷宫。我们需要从后向(从最小的迷宫)解决它们。每个迷宫都可以通过以下规则解决:

• 如果我们在当前象限中的点位于任何极值(意味着任何坐标的分量是象限的最低或最高)，我们将其留在原处，否则检查下一个点
• 如果我们的点向下或在当前象限的中间，那么我们将移动到象限的最低中点(这些相对于先前定义的方向，即:如果我们的方向是向上的，那么我们将把我们的点移动到最上面中点)
• 如果我们的点向上(在相对方向上)，我们必须将它移动到最上面的中间点

1. 存储这些移动，我们检查两个数组中是否有属于两个点的公共(public)元素:

• 如果不是，我们计算两个端点之间的距离，然后将两个移动列表中的所有距离相加(在此列表中，每个距离都可以计算为坐标分量减法，即:abs(x1-x2) + abs (y1-y2))
• 如果我们有共同元素，那么我们删除包括共同元素在内的所有移动，并按照之前提到的点计算距离

这个解决方案是可以优化的，它只是为了展示和开始的想法。

编辑:这是我在 Swift3 中对上述解决方案的实现:https://codility.com/demo/results/training9WWFXU-EWC/