雙人格子穿越遊戲

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)

我的做法我做了貪心方法以及從給定的球B(i)（從i = 1 to n開始）計算的距離p1和p2，並將最小值添加到輸出並相應地更新玩家的位置。
但是這種方法在很多測試用例上都失敗了。

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將會選擇OSE B(4) 和p2會選擇B(1), B(2), B(3)
輸出將5
注：當玩家選擇一個球，他移動到該點。

P.P.S.經過討論，我相信沒有線性時間解決方案存在到這個問題和O（n^2）解決方案是最好的解決方案。

Answer 1

我沒有線性時間算法。但是這裏有一個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) 

規劃表：通過這種方式，我們可以通過一欄中填入整個表列

   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）。追溯，我們得到：P2 @ B4，P1 @ B3，P1 @ B2，P1 @ B1。

這是承諾的可視化。最後一列的對角線的依賴已經爲清晰起見，省略：

我將不提供的僞代碼，因爲它是非常有可能，我會混合一些索引（導致超過混亂幫幫我）。但是你應該能夠從上面的描述中編寫代碼。

Answer 2

下面是O(n^2)動態規劃的實現，與尼科的答案類似。該功能的思想是：

// 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代碼，從頭到尾填充矩陣。

// 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]));