两个球员网格遍历游戏
给定一个M * N网格和两个玩家p1和p2在网格上的位置。 有n个球放在网格上的不同位置。 设这些球的位置为B(1), B(2), B(3) ..., B(n) 。
我们需要计算选择所有球所需的最小曼哈顿距离 。 如果i < j则应按升序选择球，即如果在B(j)之前选择B(j) 。
请考虑以下示例案例：
p1 = (1, 1) p2 = (3, 4)让我们考虑球的位置为B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5)
输出将为5因为p1将首先选择B(1), B(2), B(3)并且p1将选择B(4)
我的方法
我做了一个贪婪的 方法并计算了给定球B(i)的p1和p2距离（从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) ， p2将选择B(1), B(3), B(5)
输出将是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) ， p2将选择B(1), B(2), B(3)
输出将为5。
注意： 当球员选择球时，他会移动到那一点 。
PPS经过讨论，我认为这个问题不存在线性时间解决方案 ，而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和B1以及p2和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。
这是承诺的可视化。 为清楚起见，省略了最后一列的对角线依赖关系：
我不会提供伪代码，因为我很可能会混淆一些索引（导致更多的混乱而不是帮助）。 但是你应该能够编写上面描述中的代码。
这是O(n^2)动态编程的实现，类似于Nico的答案。 该function的想法是：
// Given N positions, return total distance after a move to B(n), // where p is the position of the player not at B(n-1) f(n,p): // at the end, choose between player on prev B and the other if n == N-1: return min(d(p,B[n]), d(B[n-1],B[n])) // otherwise, return min( // either move player from previous B d(B[n-1],B[n]) + f(n+1,p), // or move player from other location, p d(p,B[n]) + f(n+1,B[n-1]) )
JavaScript代码，从最后到开头填充矩阵。 一旦完成，我们选择从一个玩家开始或另一个玩家， M[0][N]或M[0][N+1] ：
// Manhattan distance function d(a,b){ return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]); } var B = [[1,1],[2,1],[3,1],[5,5]], p1 = [1,1], p2 = [3,4]; var N = B.length; // append initial player positions to B B.push(p1); B.push(p2); // create matrix M[i][j] // i = current B, j = index of location for player not on B[i-1] var M = new Array(N); for (var i=0; i0; i--){ for (var p=0; p