二维网格中一次往返可以获得的最大积分

Question

我正在开发一个类似蛇的游戏，涉及解决以下问题：

给定 m*n 2D 网格，某些位置为 1，而其他位置为零。蛇从 (0,0) 开始，向目的地 (m-1,n-1) 前进。每一步只能向右或向下。一旦到达(m-1,n-1)，就需要回到(0,0)，并且每一步只能向左或向上。此往返最多可获得多少积分？

如果只是单程，可以用动态规划轻松解决：max_gain(i,j)=max(max_gain(i+1,j),max_gain(i,j+1))+loc\ [i\]\[j\]。然而，在我的问题中，这是一次往返，一次回程，我们必须排除在前往目的地的途中已经采取的点。输入大小（m 和 n）约为 1K，因此暴力破解它是不切实际的。

Answer 1

本题关键：记录两条蛇的位置。

我们定义：

sol(k, x1, x2) is answer for a k steps trip, where snake1 is in point(x1, k - x1) and snake2 is in point(x2, k - x2)

所以我们有：

if x1 = x2 #snake in same location
  sol(k, x1, x2) = max(sol(k-1, x1, x2)
                       , sol(k-1, x1-1, x2)
                       , sol(k-1, x1, x2-1)
                       , sol(k-1, x1-1, x2-1))
                   + array[x1][k-x1]
else
  sol(k, x1, x2) = max(sol(k-1, x1, x2)
                       , sol(k-1, x1-1, x2)
                       , sol(k-1, x1, x2-1)
                       , sol(k-1, x1-1, x2-1))
                   + array[x1][k-x1] + array[x2][k-x2]

那么我们可以通过动态规划来解决这个问题。

此外，我们可以发现：最优解中没有相交。

因为，如果一个解存在交集，我们可以找到另一个可以覆盖更大区域而没有交集的解。

方法是，让一条蛇向下而不是向右，避免交叉，这样可以覆盖更大的区域。

例如：

蓝色网格代表蛇 1，绿色网格代表蛇 2，青色网格代表两条蛇都走过。

如果我们有路径：

那么我们可以改为：

这使得覆盖面积更大。

所以，在我们的解决方案中，我们只关心 x1 < x2(except the start and end point).

的解决方案

我写了一段Python代码，具体你查看一下：

def sol(array):
    mem = {}

    def _sol(k, x1, x2):
        y1 = k - x1
        y2 = k - x2
        if x1 < 0 or x2 < 0 or y1 < 0 or y2 < 0:
            return 0
        if x1 >= x2 and k != 0 and k != total_step:
            return 0
        if mem.get((k, x1, x2)) is not None:
            return mem[(k, x1, x2)]
        ans = 0
        if x1 == x2:
            ans += array[x1][y1]
        else:
            ans += array[x1][y1] + array[x2][y2]
        ans += max(_sol(k - 1, x1, x2), _sol(k - 1, x1 - 1, x2 - 1), _sol(k - 1, x1 - 1, x2), _sol(k - 1, x1, x2 - 1))
        mem[(k, x1, x2)] = ans
        return ans
    total_step = len(array) + len(array[0]) - 2
    x = len(array) - 1
    return _sol(total_step, x, x)


test = [
    [1, 1, 1, 0, 1]
    , [0, 0, 1, 0, 1]
    , [1, 0, 1, 0, 1]
    , [1, 0, 1, 0, 1]
    , [1, 1, 1, 1, 1]
]

print(sol(test))