有谁能给我一个提示，告诉我如何从Codibility着手完成以下任务：https://codility.com/programmers/task/hilbert_maze/
通过使用BFS生成迷宫和搜索最短路径，我将能够找到最短路径，但是由于最坏情况下的时间复杂度预计为O（n），所以我认为这不是正确的去路。BFS的时间复杂度为O（v v＋ee），其中V是顶点数和E的边数。例如，如果n=3，我们有一个17x17大小的网格，很明显，我们不能在3步内找到路径。
因此，所指示的时间复杂度是错误的，应该是类似于M^ 2的，或者有一个简单的技巧来简单地计算两点之间的距离而不使用图算法。我找到了一些算法来计算2个给定点的hilbert距离（如果这是这里需要的话），这些算法使用位操作等，但根本无法理解它们。此外，我认为任务的目的是找出如何计算距离和不使用现有公式。
有没有人解决了这个问题，可以帮我更进一步？谢谢！
最佳答案
这是我想出的解决办法：
每个点的位置都可以由象限数组及其方向（它将有N个元素）定义—每个元素表示前一象限中的象限整个迷宫有向上的方向
您需要为这两个点定义此数组。例如：如果n=2，且该点位于左下象限，则该点将具有向左的方向。我们取这个象限，旋转坐标系，使其方向相同这样我们就定义了新系统中的下一个象限和方向对。因此，如果我们的点在左下方象限，那么它的方向是向左的，但由于这是相对于我们之前的方向（也是向左的），这将成为一个向上的方向。
在这一点上，我们有所有的象限和方向到包含我们的点的最小迷宫。从后面（从最小的迷宫）我们需要解决它们。每个迷宫都可以通过以下规则解决：
如果我们当前象限中的点位于任何一个极端（意味着坐标的任何部分都是象限的最低或最高点），我们将其保留在原来的位置，否则检查下一个点
如果我们的点是向下的或在当前象限的中间，那么我们移动到象限的最低点（这些相对于先前定义的方向，即：如果我们的方向是向上的，那么我们将在最上面的中点移动我们的点）
如果我们的点是向上的（在相对方向上），我们就必须把它移到最上面的中间点
存储这些移动时，我们会检查两个数组中是否有属于两点的任何公共元素：
如果没有，我们计算两个端点之间的距离，并将两个移动列表的所有距离相加（在这个列表中，每个距离都可以计算为坐标分量减法，即：abs（x1-x2）+abs（y1-y2））
如果我们有共同的元素，那么我们删除之后的每一步，包括共同的元素，然后我们计算前面提到的距离
这个解决方案是可以优化的，它只意味着现在和想法开始。
编辑：这是我在swift3中实现上述解决方案的方法：https://codility.com/demo/results/training9WWFXU-EWC/
关于algorithm - HilbertMaze关于Codility的任务，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38769929/