1

谁能给我一个关于如何从 Codility 处理以下任务的提示：https ://codility.com/programmers/task/hilbert_maze/

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

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

有没有人解决了这个任务并且可以进一步帮助我？谢谢！

4

1 回答 1

2

这是我想出的解决方案：

  1. 每个点的位置可以由一个象限数组及其方向（它将有 N 个元素）定义 - 每个元素代表前一个象限中的象限。整个迷宫向上
  2. 您需要为这两个点定义此数组。例如：如果 N = 2 并且该点位于左下象限，那么它将具有向左的方向。我们采用这个象限并旋转我们的坐标系，使其方向相同。通过这种方式，我们在新系统中定义了下一个象限和方向对。因此，如果我们的点位于左下象限，那么它将具有向左的方向，但由于这是相对于我们之前的方向（也是向左），这将成为向上的方向。

  3. 在这一点上，我们拥有所有象限和方向，直到包含我们的点的最小迷宫。从后面（从最小的迷宫）我们需要解决它们。每个迷宫都可以通过以下规则解决：

    • 如果我们当前象限中的点位于任何极端（意味着任何坐标的组件是象限的最低或最高），我们将其保留在原处，否则检查下一个点
    • 如果我们的点向下或在当前象限的中间，那么我们将移动到象限的最低中间点（这些相对于先前定义的方向，即：如果我们的方向向上，那么我们将把我们的点移动到最高中间点）
    • 如果我们的点是向上的（在相对方向上），我们将不得不将它移动到最高的中间点

  4. 存储这些移动，我们检查在属于两个点的两个数组中是否有任何公共元素：

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

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

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

于 2017-05-09T08:27:29.003 回答