javascript - “超出最大调用堆栈大小”正确的方法但效率不够？Codewars Kata “阻止僵尸启示录！”

Question

我正在尝试解决这个 kata- https://www.codewars.com/kata/stop-the-zombie-apocalypse/train/javascript

我想我有一个应该可以工作的方法，但是太慢/效率低下，并且我收到错误“超出最大调用堆栈大小”。我将非常感谢所有尽可能愚蠢的回应，因为我是新手。如果你能指出我这样做的不同方式的方向，或者最好以某种方式调整我的方法。

function findZombies(matrix) {
    var n = matrix.length;
    var value = 0;
    //create 2 new arrays with 2 extras row and columns
    var arr1 = [...Array(n + 2)].map(e => Array(n + 2).fill(value));
    var arr2 = [...Array(n + 2)].map(e => Array(n + 2).fill(value));

    //change arr1 so that all infected numbers = 2, everything else = 0 
    //leaving first and last rows and columns blank 
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if (matrix[i][j] == matrix[0][0]) {
                arr1[i + 1][j + 1] = 2;
            }
        }
    }
    //if element in arr1 has a link back to arr[1][1] call the function recursively until there is no link
    //Then return arr2 with changed elements.
    function recur(arr1, arr2, i, j) {
        if (arr1[i][j] == 2 && arr1[i][j] == arr1[i + 1][j]) {
            arr2[i][j] = 1;
            recur(arr1, arr2, (i + 1), j)
        }
        if (arr1[i][j] == 2 && arr1[i][j] == arr1[i][j + 1]) {
            arr2[i][j] = 1;
            recur(arr1, arr2, i, (j + 1))
        }
        if (arr1[i][j] == 2 && arr1[i][j] == arr1[i - 1][j]) {
            arr2[i][j] = 1;
            recur(arr1, arr2, (i - 1), j)
        }
        if (arr1[i][j] == 2 && arr1[i][j] == arr1[i][j - 1]) {
            arr2[i][j] = 1;
            recur(arr1, arr2, i, (j - 1))
        } else {
            return arr2;
            console.log(arr2)
        }
    }

    recur(arr1, arr2, 1, 1);

    //clean up array by removing empty outside rows and columns
    arr2.shift();
    arr2.pop();
    for (var i = 0; i < n; i++) {
        arr2[i].shift();
        arr2[i].pop()
    }
    console.log(arr2);
}

var matrix = [
    [9, 1, 2],
    [9, 9, 9],
    [7, 4, 9],
    [7, 9, 7]
];

var matrix2 = [
    [8, 2, 3, 8, 8],
    [8, 0, 8, 8, 8],
    [1, 2, 8, 4, 8],
    [8, 2, 3, 8, 8],
    [8, 8, 8, 0, 5]
];

findZombies(matrix)

标签： javascriptarrays

Answer 1

您可以将所有有效点（僵尸）存储在包含所有僵尸及其相邻僵尸的嵌套哈希表中。

最后从已知的zombie at 开始，[0][0]获取ahsh 表的数组来访问所有连接的字段。为了防止访问已经访问过的项目，请将数组替换为undefined.

function findZombies(matrix) {
    function go([i, j]) {
        if (!tree[i] || !tree[i][j]) return;
        result[i][j] = 1;
        var temp = tree[i][j];
        tree[i][j] = undefined;
        temp.forEach(go);
    }

    var i, j,
        result = [],
        zombie = matrix[0][0],
        tree = {};

    for (i = 0; i < matrix.length; i++) {
        result.push([]);
        for (j = 0; j < matrix[i].length; j++) {
            result[i].push(0);
            if (matrix[i][j] !== zombie) continue;
            if (!tree[i]) tree[i] = {};
            tree[i][j] = [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]].filter(([x, y]) => matrix[x] && matrix[x][y] === zombie);
        }
    }

    go([0, 0]);

    return result;
}

var matrix = [[9, 1, 2, 3, 4, 1, 2, 9], [9, 9, 9, 2, 1, 5, 9, 9], [9, 2, 9, 3, 7, 9, 1, 9], [6, 9, 9, 9, 0, 9, 2, 9], [5, 4, 3, 9, 9, 9, 4, 9], [9, 3, 9, 5, 8, 9, 9, 9], [9, 9, 9, 9, 9, 9, 7, 9], [9, 9, 1, 2, 3, 9, 8, 9]],
    result = findZombies(matrix);

result.forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }