algorithm - 最大化网格上螺旋路径的总和

Question

让我们将螺旋路径定义为运动处于 [右、下、左、上、右、下、左、上...] 循环中的人(请注意，您不一定需要从对，只有那个权利必须在 up 之后，down 在 right 之后，依此类推)。但是，路径不得与自身相交。

给定一个网格，你如何找到遍历这样一条路径可以获得的最大总和？

例如，如果网格是

-5   -4   -3

 3     2    1

 -1    2    4

最大化和的螺旋路径是

-5   -4   -3

 3     2    1

 -1    2    4

路径如下:{3, 2, 1, 4, 2}

---

我的想法是，这可以通过某种前缀和方法来解决，但我不太确定如何处理它。另一个想法是从每个点运行深度优先搜索，但这对算法来说效率太低。

Answer 1

让我们按顺时针顺序向外构建螺旋(逆时针情况类似)。构建过程的状态可以用三个变量来描述:

• 到目前为止螺旋的边界框
• 现职
• 当前方向(北、东、南、西)

我们最多可以进行两种不同的移动:

• 在当前方向上更进一步
• 顺时针切换方向并朝新方向迈出一步。仅当我们已经通过边界框的边界时才允许这样做

有O(n^4)个边界框，当前位置总是在框的边界，所以这产生了一个O(n^5)个时间和空间的DP算法。

我们可以通过注意到除最后一条线段之外的所有线段都将完全覆盖当前边界框的一侧来消除一维，因此我们可以将 f(x1, y1, x2, y2, d) 定义为最大总和带有边界框 (x1, y1), (x2, y2) 的螺旋线，其中当前位置位于由当前位置 d 唯一定义的角中。

接下来的 Action 是:

• 在当前方向上进一步走一步，扩展边界框
• 切换方向，一直走到边界框的尽头

对于第二步，我们需要在 O(1) 中计算部分行和列的总和，这通过一些预处理很容易做到。我们还需要为螺旋的最后一段引入一个特殊情况，因为在那里我们不能到达边界框的边缘。整个算法可以在O(n^4)中实现。