多维数组填充

Question

我正在尝试填充多维数组中的区域，但不确定该方法。

例如，我有以下数组：

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 0, 0, 0, 0, 2, 0, 0],
    [0, 2, 0, 2, 0, 0, 2, 0, 0],
    [0, 2, 0, 0, 2, 0, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

然后，我尝试从X和Y位置获取数字，并使用给定的数字（例如1）填充所有这些数字（即0），这将导致以下数组：

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 1, 1, 1, 1, 2, 0, 0],
    [0, 2, 1, 2, 1, 1, 2, 0, 0],
    [0, 2, 1, 1, 2, 1, 2, 0, 0],
    [0, 0, 2, 1, 1, 1, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

基本上只是将该区域内所有彼此相邻的数字（0）替换为（1）。

用JavaScript执行此操作的正确方法是什么？

Answer 1

假设您已获得一个起始位置，然后想要向上/向下，向左/向右填充包含相同值的所有相邻值，则可以执行以下操作：

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 0, 0, 0, 0, 2, 0, 0],
    [0, 2, 0, 2, 0, 0, 2, 0, 0],
    [0, 2, 0, 0, 2, 0, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

function fill(data, x, y, newValue) {
    // get target value
    var target = data[x][y];

    function flow(x,y) {
        // bounds check what we were passed
        if (x >= 0 && x < data.length && y >= 0 && y < data[x].length) {
            if (data[x][y] === target) {
                data[x][y] = newValue;
                flow(x-1, y);    // check up
                flow(x+1, y);    // check down
                flow(x, y-1);    // check left
                flow(x, y+1);    // check right
            }
        }
    }

    flow(x,y);
}

fill(map, 2, 2, 1);

工作演示：http :
//jsfiddle.net/jfriend00/C83AT/

这是一个不使用递归的版本，似乎适用于大型数据集。您的大型测试数据集不是一个非常有趣的测试模式，因此我不会说这是最终测试，但它似乎适用于小型和大型数据集：

大数据示例：http :
//jsfiddle.net/jfriend00/8mrhN/

小数据示例：http：//jsfiddle.net/jfriend00/BFTub/（更易于查看结果）

function fill(data, x, y, newValue) {
    // get target value
    var target = data[x][y];
    // maintain list of cells to process
    // put the starting cell in the queue
    var queue = [{x:x, y:y}], item;

    while (queue.length) {
        item = queue.shift();
        x = item.x;
        y = item.y;
        if (data[x][y] === target) {
            data[x][y] = newValue;
            // up
            if (x > 0) {
                queue.push({x:x-1, y:y})
            }
            // down
            if (x + 1 < data.length) {
                queue.push({x:x+1, y:y})
            }
            // left
            if (y > 0) {
                queue.push({x:x, y:y-1});
            }
            // right
            if (y + 1 < data[x].length) {
                queue.push({x:x, y:y+1});
            }
        }
    }
}

可以通过在将该值放入队列之前对其进行测试并按照给定的方向进行操作，直到找到不匹配的值（如果需要），从而进一步优化性能。