Javascript 使用递归的洪水填充算法

Question

我有一个 5 X 5 矩阵，其中 1 代表陆地，0 代表水。需要创建一个函数来遍历矩阵和 returns 它找到的土地数量。需要忽略对角线 1。

我被我的程序卡住了。非常感谢帮助。

var arr = [
    [1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 1, 1]
];

我写了一个函数，它使用上面的矩阵来查找土地数量。

function findLand(arr) {

var check = [],
    cntr = 0;

for(let i=0 ;i<arr.length; i++) {
    check = [];
    traverse(i, 0);
}
function traverse(x, y) {
    if(x<0 || y<0 || x > arr.length-1 || y > arr[0].length-1) {
        return;
    }

    if(arr[x][y]!=1 || check.indexOf(x+'_'+y)!=-1) {
        return;
    }
    check.push(x+'_'+y);

    traverse(x, y+1);
    traverse(x, y-1);
    traverse(x-1, y);
    traverse(x+1, y);
}

}

findLand(matrix)

Answer 1

这是获取陆地块的数量和坐标的方法。您需要遍历整个数组 — 现在您只遍历第一列，因此您会错过不是从该边缘开始的陆地块。每次迭代都可以创建一个新的空 current 数组。最后，您将该数组推入数组 'lands' ，这将得到您的最终结果。我们还将保留一个 visited 数组，这样您就不必遍历 lands 矩阵：

var arr = [
    [1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 1, 1]
];

function findLand(arr) {
    var lands = [],        // the current group
        visited = new Set  // coords we've seen (set is quicker to lookup)
 
    // iterate the rows AND columns
    for(let i=0; i<arr.length; i++) {
        for(let j=0; j < arr[i].length; j++){
            if (visited.has(i+'_'+j)) continue // don't call function on visited coords
            let land = traverse(i,j)
            if(land) {                // land will be undefined if traverse returns undefined
                lands.push(land);
            }
        } 
    }
    function traverse(x, y, current = []) { // keep current local
        if(x<0 || y<0 || x > arr.length-1 || y > arr[0].length-1) {
            return;
        }
        if(arr[x][y]!=1 || visited.has(x+'_'+y)) {
            return;
        }
        current.push(x+'_'+y);
        visited.add(x+'_'+y)
        traverse(x, y+1, current);
        traverse(x, y-1, current);
        traverse(x-1, y, current);
        traverse(x+1, y, current);
        return current   // should hold one complete land mass
    }
    return lands
}

let lands = findLand(arr)
console.log("lands found: ", lands.length )
console.log("lands: ", lands)

Javascript 使用递归的洪水填充算法

Javascript Flood fill algorithm using recursion

javascript

recursion

flood-fill