使2个机器人在网格中收集大部分重量，而不从左上角到右下角重叠。

Question

假设下面有这样一个网格(它可以是任意m大小的网格)。机器人1和2只能从S移动到X。你如何在算法上使机器人在不重叠的情况下收集最多的重量？机器人每次必须同时移动(它必须移动，不能跳过转弯/s)。我知道它们不能重叠，它们不可能有相同的y值。

S 1 4 3 3

1 2 4 6 4

2 4 2 1 5

2 1 5 6 1

9 1 2 3 X

我将以最佳的时间和空间复杂性接受第一个答案。

Answer 1

我在O(n^3)时间点O(n^2)空间中解决了这个问题。

其解释是，将有最大的n个回合。您只需要存储前一个回合来计算下一个回合。在每个回合中，可能有最多n^2的有效位置组合。由于您必须经过n^2组合n次，所以运行时间是n^3。

Answer 2

在每一个转折点，最多有4个可能的动作：

• 机器人1下，机器人2下
• 机器人1下，机器人2右
• 机器人1右，机器人2下
• 机器人1右，机器人2右

下面是用Java实现的递归解决方案。对于给定的位置，最佳得分是位于该位置的权重之和+四种可能移动中的最佳得分：

public class Robots
{
    private int[][] grid;
    private int size;

    /*
    * Check if both robots occupy a valid position
    */
    private boolean isValid(int x1, int y1, int x2, int y2)
    {
        if(x1==size || y1==size || x2==size || y2==size)
            return false;
        if(x1==x2)
            return false;
        return true;
    }

    private int getMax(int s1, int s2, int s3, int s4)
    {
        int max = s1;
        if(s2>max)
            max = s2;
        if(s3>max)
            max = s3;
        if(s4>max)
            max = s4;
        return max;
    }

    /*
    * Computes the best score possible from a starting position
    */
    private int getBestScore(int x1, int y1, int x2, int y2)
    {
        if(!isValid(x1, y1, x2, y2))
            return 0;
        int s1 = getBestScore(x1+1, y1, x2+1, y2); // robot 1 down, robot 2 down
        int s2 = getBestScore(x1+1, y1, x2, y2+1); // robot 1 down, robot 2 right
        int s3 = getBestScore(x1, y1+1, x2+1, y2); // robot 1 right, robot 2 down
        int s4 = getBestScore(x1, y1+1, x2, y2+1); // robot 1 right, robot 2 right
        return grid[x1][y1] + grid[x2][y2] + getMax(s1, s2, s3, s4);
    }

    public int solve(int[][] grid)
    {
        this.grid = grid;
        size = grid.length;
        return getBestScore(1, 0, 0, 1);
    }

    public static void main(String[] args)
    {
        int[][] grid = {{0,1,4,3,3}, {1,2,4,6,4}, {2,4,2,1,5}, {2,1,5,6,1}, {9,1,2,3,0}};

        Robots robots = new Robots();
        System.out.println("Best score = " + robots.solve(grid));
    }
}

问题中给出的例子的结果是：

Best score = 48

Answer 3

在O(m^3)时间和O(m^2)空间中求解是可能的，就像一个机器人可以在O(m^2)时间和O(m)空间中求解一样。

对于一个机器人，在k步(对角线)之后有一个可能值的数组，然后通过考虑可能的两步移动，在k+1步骤之后构造可能的值。

对于两个机器人，一个机器人在一个轴上的位置和另一个机器人在另一个轴上的位置代替了k步后的矩阵--这就给出了空间需求，每个矩阵元素最多将基于前面步骤中的2x2，并且有O(m)步到达目的地，因此它应该是O(m^3)时间。