Сравнение двух бинарных матричных сеток для совпадающих островков (связанных областей «1»)

Question

Это очень похоже на эту задачу «Количество островов» JavaScript https://codereview.stackexchange.com/questions/201530/count-number-of-islands-2d-grid.

Учитывая две сетки, где каждая ячейка сетки содержит либо «0», либо «1».Если две ячейки имеют общую сторону, то они смежные.Клетки, которые содержат «1», образуют связанную область (или остров, как обычно называют), если любая ячейка в этой области может быть достигнута путем перемещения через соседние ячейки, которые содержат «1».Наложите первую сетку на вторую, и если область первой сетки полностью совпадает с областью второй сетки, области сопоставляются.Подсчитать общее количество таких совпадающих областей во второй сетке

Вот пример:

Grid 1
0 0 1
0 1 1
1 0 0

Grid 2
0 0 1
0 1 1
1 0 1

Сетка 1 формирует две области в точке {(0,2), (1,1),(1,2)} и {(2,0)}

Сетка 2 образует две области в точке {(0, 2), (1,1), (1,2), (2,2)} и {(2,0)}

Область {(2,0)} - единственная подходящая область, поэтому ответ здесь равен 1.

Это то, что я сделал ниже. Моя функция countMatches () возвращает количество связанных областей в каждой сетке, но я хочу сравнить любую связанную область в сетке 1 с областью сетки 2 и вернуть количество совпадений, то есть количество точных связанных областей, присутствующих ви то и другое.Этот результат будет одним целым числом .

Также здесь есть ссылка на кодовый блок - https://codepen.io/Baystef/pen/OqBJzG

JavaScript
function countMatches(grid1, grid2) {
    let gridOne = grid1.filter(n => typeof(n) !== 'number');
    let gridTwo = grid2.filter(n => typeof(n) !== 'number');

    //this only gives number of connected region in each grid, but what i want to get is number of islands that match perfectly when the grids are overlayed.
    return `We have ${countIslands(gridOne)} island(s) in grid 1 and ${countIslands(gridTwo)} island(s) in grid 2`
}

function countIslands(grid) {
    let markIsland = function (grid, x, y, visited) {
        if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[x].length - 1) return;

        if (visited[x][y] === true) return;
        visited[x][y] = true;

        if (grid[x][y] === '0') return;

        markIsland(grid, x - 1, y, visited);
        markIsland(grid, x + 1, y, visited);
        markIsland(grid, x, y - 1, visited);
        markIsland(grid, x, y + 1, visited);
    };

    let visited = [];

    for (let i = 0; i < grid.length; i++) {
        visited[i] = [];
    }

    let count = 0;

    for (let x = 0; x < grid.length; x++) {
        for (let y = 0; y < grid[x].length; y++) {
            if (!visited[x][y] && grid[x][y] === '1') {
                count++;
                markIsland(grid, x, y, visited);
            }
            visited[x][y] = true;
        }
    }

    return count;
}

Пример ввода сетки: -

const grid1_1 = [
    4,
    ['0', '1', '0', '0'],
    ['1', '0', '0', '1'],
    ['0', '0', '1', '1'],
    ['0', '0', '1', '1']
]
const grid2_1 = [
    4,
    ['0', '1', '0', '1'],
    ['1', '0', '0', '1'],
    ['0', '0', '1', '1'],
    ['0', '0', '1', '1']
]

const grid1_2 = [
    3,
    ['0', '0', '1'],
    ['0', '1', '1'],
    ['1', '0', '0']
]
const grid2_2 = [
    3,
    ['0', '0', '1'],
    ['0', '1', '1'],
    ['1', '0', '1']
]

Первая строка каждой сетки содержит целое числоэто размер массива сетки, то есть 4 означает, что это сетка 4 X 4.

Если я запустил функцию countMatches (grid1_1, grid2_1), она должна вернуть 2.

Причина в том, что grid1_1 имеет 3 связанных области (острова), которые являются позициями {(0,1)} , {(1,0)} and {(1,3),(2,2),(2,3),(3,2),(3,3)}

grid2_1, также имеет 3 связанных области (острова) в позициях {(0,1)}, {(1,0)} and {(0,3),(1,3),(2,2),(2,3),(3,2),(3,3)}

Регионы {(0,1)}, {(1,0)} являютсятолько две области, которые существуют исключительно в grid1_1 и grid2_1, и поэтому функция должна возвращать 2.

Answer 1

Вы можете сначала получить количество островов, а затем сравнить второй массив с массивом с пронумерованными островами.

В этом подходе используется упрощенный набор данных и массив с длиной счета островков.

В результате все истинные значения массива matches подсчитываются и перенастраиваются.

Примеры:

   a          b       congruent islands/matching areas
-------    -------    --------------------------------
0 1 0 0    0 1 0 1
2 0 0 3    1 0 0 1
0 0 3 3    0 0 1 1
0 0 3 3    0 0 1 1    3/islands 1 2 3

0 1 0 2    0 1 0 0
3 0 0 2    1 0 0 1
0 0 2 2    0 0 1 1
0 0 2 2    0 0 1 1    2/islands 1 3

0 0 1      0 0 1
0 1 1      0 1 1
2 0 0      1 0 1      2/islands 1 2

0 0 1      0 0 1
0 1 1      0 1 1
2 0 1      1 0 0      1/islands 2

function getIslands(array) {

    function test(array, i, j, count) {
        if (array[i] && array[i][j] === -1) {
            array[i][j] = count;
            test(array, i - 1, j, count);
            test(array, i + 1, j, count);
            test(array, i, j - 1, count);
            test(array, i, j + 1, count);
            return true;
        }
    }

    var count = 1,
        islands = array.map(a => a.map(v => -v));
    islands.forEach((a, i, aa) => a.forEach((_, j) => test(aa, i, j, count) && count++));
    return { islands, count: count - 1 };
}

function countMatches(array1, array2) {
    var islands = getIslands(array1),
        matches = Array.from({ length: islands.count + 1 }).fill(true);

    islands.islands.forEach((a, i) => a.forEach((v, j) => matches[v] = matches[v] && array2[i][j] && v));
    islands.islands.forEach(a => console.log(...a));
    console.log('');
    array2.forEach(a => console.log(...a));
    console.log('islands', ...matches.filter(Boolean));
    return matches.reduce((s, b) => s + !!b, 0);
}

console.log(countMatches([[0, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]], [[0, 1, 0, 1], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]]));
console.log(countMatches([[0, 1, 0, 1], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]], [[0, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]]));
console.log(countMatches([[0, 0, 1], [0, 1, 1], [1, 0, 0]], [[0, 0, 1], [0, 1, 1], [1, 0, 1]]));
console.log(countMatches([[0, 0, 1], [0, 1, 1], [1, 0, 1]], [[0, 0, 1], [0, 1, 1], [1, 0, 0]]));

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