两个球员网格遍历游戏

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)

我的方法
,我做了贪婪的 方法和计算距离p1,并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) 和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)解决方案是可用的最佳解决方案.

Answer 1

存在O(n^3)解决方案，我们可以balls[i]选择p1或p2

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));
}