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

Question

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

algorithmprefix

4

让我们将螺旋路径定义为一种运动循环方式为 [右，下，左，上，右，下，左，上，...]（注意，您不需要必须从右侧开始，只需在向上后紧随其后的是向下，在向右之后紧随其后的是向左，以此类推）。但是，路径不能与自身相交。

给定一个网格，如何找到通过这样的路径可以达到的最大总和？

例如，如果网格为

-5 -4 -3 3 2 1 -1 2 4

最大化总和的螺旋路径是

-5 -4 -3 3 2 1 -1 2 4

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

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

- 1110101001

这个问题应该在 Stack Exchange 网络的另一个站点上发表。 - John3136

对我来说，这似乎是一个有趣的算法问题。以下是一个观察结果：任何螺旋路径都可以分为两个部分，第一个部分是“扩张”螺旋，第二个部分是“收缩”螺旋。（这两个部分中的任何一个都可以长度为0。）由于任何矩形都可以完全被任一种类型的螺旋覆盖，因此一种启发式方法是查看所有共享至少1个公共边界行或列的矩形对，通过沿着共享边界连接2个矩形的额外单元格，并取最大值。（在O（n ^ 2）预计算后，矩形和为O（1）。） - j_random_hacker

请注意，这种方法并不是最优的，因为它忽略了可能跳过某些行和/或列的螺旋形式。目前还不确定如何有效地适应这种情况。 - j_random_hacker

这只是关于子矩阵的动态规划，但它并不美观。 - Niklas B.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niklas B. · Accepted Answer

让我们按顺时针方向构建螺旋（逆时针情况类似）。建筑过程的状态可以用三个变量描述：

- 螺旋迄今为止的边界框 - 当前位置 - 当前方向（北、东、南、西）

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

- 沿着当前方向再走一步 - 顺时针切换方向并朝新方向走一步。只有当我们已经越过边界框时才允许这样做。

由于存在 O(n^4) 个边界框，当前位置总是在框的边界上，因此这会产生一个 O(n^5) 的时间和空间 DP 算法。

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

接下来的移动如下：

向当前方向再走一步，扩展边界框
改变方向，一直走到边界框的末尾

对于第二个移动，我们需要在O(1)时间内计算部分行和列的总和，这可以通过预处理轻松完成。我们还需要为螺旋的最后一段引入一个特殊情况，因为在那里我们可以不走到边界框的边缘。整个算法的实现可以在O(n^4)中完成。