javascript - "Maximum call stack size exceeded"方法正确但效率不够？ Codewars 卡塔 “Stop the Zombie Apocalypse!”

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)

Answer 1

您可以将所有有效点(僵尸)与所有僵尸及其相邻僵尸存储在嵌套哈希表中。

最后从[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; }