两人网格穿越游戏

Given a M * N两名玩家的网格和位置p1 and p2在网格上。有 n 个球放置在网格上的不同位置。设这些球的位置为B(1), B(2), B(3) ..., B(n).

我们需要计算曼哈顿最短距离需要挑选所有的球。应按升序挑选球，即如果B(i)之前被挑选过B(j) if i < j.

考虑以下示例案例：
p1 = (1, 1) p2 = (3, 4)让我们将球的位置考虑为B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5)
Output将5因为p1会首先选择B(1), B(2), B(3) and p1会选择B(4)

我的方法
我做了一个greedy approach和计算出的距离p1 and p2从给定的球B(i)（从...开始i = 1 to n）并将最小值添加到输出中并相应地更新玩家的位置。
但这种方法对于很多测试用例来说都失败了。

PS：这个问题是在我过去的一次采访中被问到的O(n)这一问题的解决有望得到解决。

编辑：更多测试用例可以是这样的
p1 = (1,1) p2 = (3,5)
B(1) = (3, 3), B(2) = (1, 1), B(3) = (4, 5), B(4) = (2, 1), B(5) = (4, 3).
在这种情况下p1会选择B(2), B(4) and p2会选择B(1), B(3), B(5)
Output将会是8。

p1 = (1,1) p2 = (3,4)
B(1) = (2, 2), B(2) = (3, 2), B(3) = (4, 2), B(4) = (1, 1)
在这种情况下p1会选择B(4) and p2会选择B(1), B(2), B(3)
Output将是 5。
Note: 当玩家选择一个球时，他会移动到该点.

附言经过讨论我相信不存在线性时间解对于这个问题和O(n^2) 解决方案是可用的最佳解决方案。

我没有线性时间算法。但这里有一个 n² 动态程序：

对于每个时间点（即每个球），您可以选择任何一名球员来接球。我们应该维护的一个有趣的信息是此时其他玩家的位置。所以我们的时间状态Ti由以下任一组成{P1, P2}以及其他玩家的位置。现在，我们希望通过计算下表（使用您的第一个示例）来逐步计算每个时间点和每个可能状态的最小距离：

             T1   T2   T3   T4
----------+--------------------
P1; P2@p2 |  0
P1; P2@B1 |
P1; P2@B2 |
P1; P2@B3 |
P2; P1@p1 |  5
P2; P1@B1 |
P2; P1@B2 |
P2; P1@B3 |

两个初始值是之间的距离p1 and B1 and p2 and B1， 分别。

从每个状态，我们都可以直接前往正确的相邻单元格。这相当于将相应的球员移至新球，并将另一名球员保持在当前位置。成本的变化是当前球和新球之间的距离。

对于每个新专栏，我们在末尾都有一个新条目（对于两名玩家）。这意味着另一名球员拿起了最后一个球，而当前球员可能在任何地方。所以我们要找到当前玩家所有可能位置到当前球的最小距离。我将在这篇文章的末尾对此进行可视化。这样，我们就可以逐列填充整个表格：

示例（再次来自您的问题）

p1 = (1, 1)
p2 = (3, 4) 
B(1) = (1, 1)
B(2) = (2, 1)
B(3) = (3, 1)
B(4) = (5, 5)

DP表：

             T1   T2            T3               T4
----------+---------------------------------------------------------
P1; P2@p2 |  0    0+1=2         1+1=2            2+6=8
P1; P2@B1 |       min(5+1)=6    6+1=7            7+6=13
P1; P2@B2 |                     min(6+2,4+2)=6   6+6=12
P1; P2@B3 |                                      min(7+8,5+8,4+7)=11
P2; P1@p1 |  5   5+1=6          6+1=7            7+6=13
P2; P1@B1 |      min(0+4)=4     4+1=5            5+6=11
P2; P1@B2 |                     min(1+3,6+2)=4   4+6=10
P2; P1@B3 |                                      min(2+3,7+8,6+7)=5

最后一列的最小值是5（即收集所有球的最小距离是 5）。回溯，我们得到：P2@B4，P1@B3，P1@B2，P1@B1。

这是承诺的可视化。为了清楚起见，最后一列的对角线依赖性已被省略：

我不会提供伪代码，因为我很可能会混淆一些索引（导致更多的混乱而不是帮助）。但您应该能够根据上面的描述编写代码。