两人网格遍历游戏

Question

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

我们需要计算拾取所有球所需的最小曼哈顿距离。应该按升序挑选球，即如果 B(i) 在 B(j) 之前被挑选，如果 i < 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)

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

P.S：这个问题在我过去的一次采访中被问到，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。
注意：当玩家选择一个球时，他会移动到那个点。

P.P.S。经过讨论，我相信 不存在线性时间解决方案 这个问题，O(n^2) 解决方案 是可用的最佳解决方案。

Answer 1

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

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

             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之间的距离。

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

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

示例（同样来自您的问题）

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

DP table:

             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.

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

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

Answer 2

这是一个 O(n^2) 动态规划的实现，类似于 Nico 的回答。函数的思路是：

// 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; i<N; i++){
  M[i] = new Array(N + 2);
}

// at the last B, choose between player on prev B and the other
for (var p=0; p<N+2; p++){
  M[N-1][p] = Math.min(d(B[p],B[N-1]), d(B[N-2],B[N-1]));
}

// either move player from prev B, or from other position, p
for (var i=N-2; i>0; i--){
  for (var p=0; p<N+2; p++){
    M[i][p] = Math.min(d(B[i-1],B[i]) + M[i+1][p],
                       d(B[p],B[i]) + M[i+1][i-1]);
  }
}

// on the first B, choose between the first and second players
M[0][N] = d(B[N],B[0]) + M[1][N+1];
M[0][N+1] = d(B[N+1],B[0]) + M[1][N];

for (var i=0; i<N; i++)
  console.log(JSON.stringify(M[i]));

Answer 3

有 O(n^3) 解决方案，我们可以从 p1 或 p2

中选择 balls[i]


let memo = {};

function findMinDistance (p1, p2, balls, n) {
    if (n === balls.length) return 0;
    const key = `${n}_${p1}_${p2}`;
    
    function dis (a, b) {
    return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
    
   if (memo[key]) {
       return memo[key]
   }
    
    const minDis = Math.min(
        dis(p1, balls[n]) + findMinDis (balls[n], p2, balls, n + 1),
        dis(p2, balls[n]) + findMinDis (p1, balls[n], balls, n + 1)
    );
    
    memo[key] = minDis;
    return minDis
}


function solve() {
    let p1 = [1,1];
    let p2 = [3,4];
    let balls = [ [2,2], [3,2], [4,2], [1,1] ];
    
    console.log(findMinDis(p1, p2, balls, 0));
}

两人网格遍历游戏

Two player grid traversal game

java

algorithm

math

dynamic-programming

greedy