Javascript алгоритм заполнения Flood с использованием рекурсии - PullRequest
Новая
       41

Javascript алгоритм заполнения Flood с использованием рекурсии

0 голосов
/ 30 сентября 2018

У меня есть матрица 5 X 5, в которой 1 представляет землю, а 0 - воду.Нужно создать функцию, которая будет перебирать матрицу и возвращать количество найденных земель.Необходимо игнорировать диагональ 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)

1 Ответ

0 голосов
/ 30 сентября 2018

Вот способ получить и счет, и координаты масс суши.Вам нужно выполнить итерацию по всему массиву - сейчас вы выполняете итерацию только по первому столбцу, так что вы пропустите массы суши, которые не начались с этого края.На каждой итерации вы можете создать новый пустой массив current.В конце вы вставите этот массив в массив'lands ', который будет иметь ваш окончательный результат.Мы также сохраним массив visited, чтобы вам не приходилось перебирать матрицу земель: 

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)
...