多维数组填充 [英] Multidimensional array fill

问题描述

我想在一个多维数组来填充一个区域，而不是确定的方法。

I'm trying to fill an area in a multidimensional array and not sure on the approach.

例如我有以下的数组：

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位置的数量，并填写所有这些数字（即0）与一些给定的，如1，这将导致下面的数组：

And then I am trying to get the number from X and Y position and fill all those numbers (which is 0) with a number given such as 1, which will result in the following array:

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）区域内。

Basically just replacing all numbers next to each other (0) with (1) within that area.

什么是用JavaScript这样做的正确方法？

What is the correct way to do this with JavaScript?

推荐答案

假设你给出一个首发位置，你想，然后填写所有相邻值上/下，左/右，包含相同的值，你可以做是这样的：

Assuming you're given a starting position and you want to then fill all neighboring values up/down, left/right that contain the same value, you can do something like this:

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/

下面是一个不使用递归，并出现与大型数据集工作的一个版本。您的大型测试数据集是不是一个很有趣的测试模式，所以我不会说这是确凿测试，但它似乎工作同时在小型和大型数据集：

Here's a version that doesn't use recursion and appears to work with large data sets. Your large test data set wasn't a very interesting test pattern so I wouldn't say this is tested conclusively, but it seems to work on both the small and large data set:

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

小数据例如： http://jsfiddle.net/jfriend00/BFTub/ （更容易看到结果）

Small data example: http://jsfiddle.net/jfriend00/BFTub/ (easier to see the result)

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

这可能会进一步的性能，将其置于队列之前测试的值，并通过给定的方向下，直到找到一个不匹配的值进行优化，如果需要的话。

This could be optimized further for performance by testing the value before putting it in the queue and by following a given direction until you find a non-matching value, if required.

这篇关于多维数组填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！