Как написать счетчик островов?

#javascript #алгоритм #циклы

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


как мне получить количество островов, тут их 2 один вверху справа(одиночный) и один
большой весь последний ряд и первая колонка. я обращался к элементам при помощи 2-ого
цикла.

for (let i = 0; i < arr.length; i++) {
for (let x = 0; i < arr[i].length; x++) {
        if(...){
      }
   }
}


Так вот я никак не могу придумать условие помогите.
    

Ответы

Ответ 1

Тут нужно использовать алгоритм заливки изображения. Логика такая:


Обход каждого пиксела.
Если он == 1, то заливаем фигуру из единиц нулями, при этом инкрементим счётчик островов.
В конце обхода получаем количество островов, и матрицу, заполненную нулями.


Алгоритм заливки там описан на C, но как ни странно - будет работать на JS, всего
лишь заменив объявление функции, я капельку доработал, оставив только одну глобальную
переменную screenBuffer:

//Recursive 4-way floodfill, crashes if recursion stack is full 
function floodFill4(x, y, newColor, oldColor = null) 
{ 
  if (!oldColor){
    oldColor = screenBuffer[x][y];
  }
  if(x >= 0 && x < screenBuffer.length && y >= 0 && y < screenBuffer[0].length &&
screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor) 
  { 
    screenBuffer[x][y] = newColor; //set color before starting recursion

    floodFill4(x + 1, y,   newColor, oldColor);
    floodFill4(x - 1, y,   newColor, oldColor);
    floodFill4(x,   y + 1, newColor, oldColor);
    floodFill4(x,   y - 1, newColor, oldColor);
  }   
}


Ответ 2

Эта задача называется поиск компонент связности графа.
Решается в несколько этапов:
- строим граф на основе матрицы.  Каждую клетку с 1 делаем вершиной,  соединяем её
ребрами с непосредственными соседями (если они есть) 
- добавляем все вершины в массив
- поиском в глубину или ширину начинаем обход с первой вершины.  Удаляем вершины
в которых побывали из массива,  добавляем их в набор вершин острова. Если обход завершён,
 а массиве ещё есть вершины,  создаём ещё один остров и начинаем обход заново с первой
оставшейся вершины.
Данный алгоритм имеет сложность по памяти и времени n,  работает даже для вложенных
бубликов


Ответ 3

Набросал реализацию. В основе "построчная заливка". Чуть-чуть упростил т.к. сама
заливка не нужна.

Добавил тестов. Если выполнить, то в консоли будет видно сколько их, какие прошли
успешно, а какие нет.

Работает просто.

Перебираем "участки земли" слева направо и сверху вниз. Т.к. перебираем именно в
этой последовательности, то для каждого участка точно знаем, что участок левее и выше
- уже рассматривались на прошлых итерациях перебора. Поэтому в поиске острова учитываем
только их.

Нашли участок для которого слева и сверху вода? - Это начало нового острова. Нашли
землю слева? - Это продолжение найденного ранее острова. Нашли выше кусок другого острова
(другого, не текущего, это важно)? - Забываем про него навсегда: он является куском
рассматриваемого.

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



function calc(arr) {
    let rows = arr.length, cols = arr[0].length; // размеры матрицы

    let islands = 0; // порядковый номер последнего из найденных островов
    let eaten = []; // острова, примкнувшие к другим на поздних итерациях поиска

    // участок земели ..
    let left = 0, // .. слева от рассматриваемого и ..
        up = 0; // .. над рассматриваемым

    // является ли искомый остров в списке ранее примкнувших
    let isEaten = function (needle) {
        for (let i = 0; i < eaten.length; i++) {
            if (eaten[i] === needle) {
                return true;
            }
        }
        return false;
    };

    // перебираем матрицу с верхнего левого в нижний правый угол
    for (let row = 0; row < rows; row++) { // построчно сверху вниз
        for (let col = 0; col < cols; col++) { // а строки по столбцам слева направо
            if (!arr[row][col]) {
                continue; // пропускаем морские участки
            }
            left = col > 0
                ? arr[row][col - 1] // определяем участок земли слева
                : 0;
            up = row > 0
                ? arr[row - 1][col] // определяем участок земли сверху
                : 0;
            if (!left && !up) { // участок земли начинает остров, если слева и сверху
нет земли
                islands++; // увеличиваем счётчик найденных островов
                arr[row][col] = islands; // запоминаем найденный участок
            } else if (left && !up) {
                arr[row][col] = left; // участок продолжает вправо ранее найденный
остров
            } else if (!left && up) {
                arr[row][col] = up; // участок продолжает вниз ранее найденный остров
            } else if (left && up && up !== 1 && !isEaten(up)) {
                arr[row][col] = left; // участок продолжает вправо ранее найденный
остров
                eaten.push(up); // а сверху к нему примыкает ранее не поглощённый
остров - поглощаем его
            }
        }
    }

    return islands - eaten.length;
}

let tests = [
    [
        [
            [1, 0, 1],
            [1, 0, 1],
            [1, 1, 1],
        ],
        1
    ],
    [
        [
            [1, 1, 1],
            [1, 1, 0],
            [1, 0, 0],
        ],
        1
    ],
    [
        [
            [1, 0, 1],
            [1, 0, 0],
            [1, 1, 1],
        ],
        2
    ],
    [
        [
            [1, 0, 1],
            [1, 0, 0],
            [1, 0, 1],
        ],
        3
    ],
    [
        [
            [1, 1, 1],
            [1, 0, 1],
            [1, 1, 1],
        ],
        1
    ],
    [
        [
            [1, 0, 1],
            [0, 1, 0],
            [1, 0, 1],
        ],
        5
    ],
    [
        [
            [1, 0, 1, 1, 1],
            [1, 0, 0, 0, 1],
            [1, 1, 1, 0, 1],
            [0, 0, 0, 0, 1],
            [1, 1, 1, 1, 1],
        ],
        2
    ],
    [
        [
            [1, 1, 1, 1, 1],
            [1, 0, 0, 0, 1],
            [1, 0, 1, 0, 1],
            [1, 0, 0, 0, 1],
            [1, 1, 1, 1, 1],
        ],
        2
    ],
    [
        [
            [1, 0, 1],
            [1, 0, 1],
            [1, 0, 1],
        ],
        2
    ],
    [
        [
            [1, 0, 1, 0, 1, 0],
            [0, 0, 1, 1, 1, 0],
            [0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0],
        ],
        2
    ],
];

let result = [];
let fails = [];
console.log(`Tests: ${tests.length}`);
for (let i = 0; i < tests.length; i++) {
    let arr = tests[i][0];
    let expected = tests[i][1];
    let actual = calc(arr);
    if (expected !== actual) {
        result.push('F');
        fails.push(`#${i}: expected = ${expected}, actual = ${actual}`);
    } else {
        result.push('.');
    }
}
console.log(result.join(''));
console.log(fails.join(`\n`));