Two player grid traversal game

问题:

Given a M * N grid and location of two players p1 and p2on grid. There are n balls placed on different positions on the grid. Let the location of these balls be B(1), B(2), B(3) ..., B(n).

We need to calculate the minumum manhattan distance required to pick all the balls. Balls should be picked in ascending order i.e if B(i) is picked before B(j) if i < j.

Consider the following sample case:
p1 = (1, 1) p2 = (3, 4) Lets consider location of balls as B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5)
Output will be 5 because p1 will first choose B(1), B(2), B(3) and p1 will choose B(4)

My Approach
I did a greedy approach and calculated distance of p1 and p2 from a given ball B(i) (starting from i = 1 to n) and added the minimum to the output and updated the position of the player accordingly.
But this approach fails for a lot of testcases.

P.S: This question was asked in one of my past interviews and O(n) solution to this problem is expected.

Edit: More testcases can be like
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).
In this case p1 will choose B(2), B(4) and p2 will choose B(1), B(3), B(5)
Output will be 8.

p1 = (1,1) p2 = (3,4)
B(1) = (2, 2), B(2) = (3, 2), B(3) = (4, 2), B(4) = (1, 1)
In this case p1 will choose B(4) and p2 will choose B(1), B(2), B(3)
Output will be 5.
Note: When player chooses a ball he moves to that point.

P.P.S. After discussion I believe no linear-time solution exists to this problem and O(n^2) solution is the best solution available.

回答1:

I don't have a linear-time algorithm. But here is a n² dynamic program:

For every point in time (i.e. for every ball), you can choose either of the players to pick up the ball. An interesting information we should maintain is the position of the other player at this time. So our state for time Ti consists of either of {P1, P2} and the location of the other player. Now, we want to incrementally calculate the minimum distance for every point in time and every possible state by computing the following table (using your first example):

             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 |

The two initial values are the distances between p1 and B1 and p2 and B1, respectively.

From every state, we can go directly to the right neighboring cell. This equals moving the according player to the new ball and keeping the other player at its current location. The change in cost is the distance between the current ball and the new ball.

And for every new column, we have a new entry at the end (for both players). This means that the other player picked up the last ball and the current player could be anywhere. So we have to find the minimum distance of all possible locations of the current player to the current ball. I'll give a visualization of this at the end of this post. This way, we can fill the entire table column by column:

Example (again from your question)

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

The minimum in the last column is 5 (i.e. the minimum distance to collect all balls is 5). Tracing back, we get: P2@B4, P1@B3, P1@B2, P1@B1.

Here is the promised visualization. The diagonal dependencies for the last column have been omitted for reasons of clarity:

I won't provide pseudo-code since it is very likely that I would mix up some indexing (leading to more confusion than help). But you should be able to write the code from the description above.

回答2:

Here's an implementation of an O(n^2) dynamic programming, similar to Nico's answer. The idea of the function is:

// 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 code, filling the matrix from the end to the beginning. Once completed, we choose between starting with one player or the other, M[0][N] or 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]));