将自行车分配给人们-第一优先（最接近的自行车最接近的人）

Question

通过网格将功能传递给骑自行车的人

[ 'c' , '_' ,'A' ,'_', '_' , '_']
[ '_' , '_' ,'a' ,'_', '_' , '_']
[ '_' , '_' ,'_' ,'_', 'b' , '_']
[ '_' , '_' ,'_' ,'_', '_' , '_']
[ 'D' , 'd' ,'_' ,'_', '_' , 'B']
[ '_' , '_' ,'_' ,'C', '_' , '_']

输出：像这样[A:1, B:3, C:8, D:1]

其中A是人，而1是到达自行车所需的步骤。

标准：

1. 最靠近自行车的人，将自行车放在第一位。
2. 不能将单个自行车分配给2个人
3. 一辆自行车到一个人的距离永远不会等于同一辆自行车到另一个人的距离。
4. 距离可以相等，但是2个不同的自行车和2个不同的人

我觉得图形表示可能更有意义

---

我的方法：

1. 查找Bikes and Person的位置并将其存储在数组中。

   person = [[0,2],[4,0],[4,5],[5,3]], bikes = [[0,0],[1,2],[2,4],[4,1]];

2. 由于最短路径为1，因此开始从最短路径为1的阵列中删除自行车和人，并将最短路径递增1。然后将人和自行车存储到结果数组中。

3. 需要继续执行步骤2，直到我们的人员数组为空

[ 'c' , '_' ,'A' ,'_', '_' , '_']
[ '_' , '_' ,'a' ,'_', '_' , '_']
[ '_' , '_' ,'_' ,'_', 'b' , '_']
[ '_' , '_' ,'_' ,'_', '_' , '_']
[ 'D' , 'd' ,'_' ,'_', '_' , 'B']
[ '_' , '_' ,'_' ,'C', '_' , '_']

Answer 1

如果我理解正确的话，你就快到了。你需要做的确实是找到人和自行车的所有组合，并测量他们的距离。然后，您根据距离对这些进行排序，然后您可以迭代它们，并在遇到某人还没有自行车但自行车仍然空闲的组合时将自行车分配给该人。这将为每个人分配不同的自行车，并首先使用最短的距离。在 javascript 中可能看起来像这样：

function findBikesForPeople(grid) {
    var rows = grid.length, cols = grid[0].length;
    var bikes = [], people = [];
    for (var row = 0; row < rows; row++) {
        for (var col = 0; col < cols; col++) {
            if (grid[row][col] === 'B') {
                bikes.push({y: row, x:col});
            }
            if (grid[row][col] === 'P') {
                people.push({y:row, x:col});
            }
        }
    }
    var combis = [];
    for (var p in people) {
        for (var b in bikes) {
            var d = distance(people[p], bikes[b]);
            combis.push({person:p, bike:b, distance:d});
        }
    }
    combis.sort(function(a,b) {return a.distance - b.distance});
    var hasBike = [], isTaken = [], assignment = [];
    for (var c in combis) {
        var person = combis[c].person, bike = combis[c].bike;
        if (!hasBike[person] && !isTaken[bike]) {
            assignment.push({person:person, 
                             px:people[person].x, py:people[person].y,
                             bike:bike,
                             bx:bikes[bike].x, by:bikes[bike].y});
            hasBike[person] = true;
            isTaken[bike] = true;
        }
    }
    return assignment;

    function distance(a, b) {
        return Math.abs(b.x - a.x) + Math.abs(b.y - a.y);
    }
}

var grid = [['B', '_', 'P', '_', '_', '_'],
            ['_', '_', 'B', '_', '_', '_'],
            ['_', '_', '_', '_', 'B', '_'],
            ['_', '_', '_', '_', '_', '_'],
            ['P', 'B', '_', '_', '_', 'P'],
            ['_', '_', '_', 'P', '_', '_']];
document.write(JSON.stringify(findBikesForPeople(grid)));

注意：我正在解释代码中显示的网格，x = 水平，y = 垂直，即 grid[y][x]，(0,0) 为左上角。