Количество островов

Продолжаем работать с матрицами и сегодня мы будем играть в великих первооткрывателей.

Сложность: 🟠 Cредняя

ℹ️ Описание


Дана матрица размером m x n, которая представляет собой карту. Каждая ячейка матрицы может принимать следующие значения:

1 — суша
0 — вода

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

Напишите функцию, которая принимает на вход матрицу и возвращает количество островов в ней.

⚠️ Ограничения

🔹В матрице может быть от 1 до 300 столбцов и колонок
🔹Допустимые значения в матрице — 0 или 1

1️⃣ Пример

Входящие данные:
[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"],
]

Ответ: 1

2️⃣ Пример

Входящие данные:
[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"],
]

Ответ: 3

✅ Решение

Для того чтобы посчитать количество островов в матрице достаточно определить хотя бы по одной точке из каждого острова.

Первым делом создадим счетчик для подсчета количества островов, который будет иметь начальное значение равное 0. Далее для подсчета необходимо перебрать все элементы матрицы и выполнить следующие проверки:

🔘 если значение элемента равно 0, то мы просто его пропускаем;

🔘 если значение равно 1, то мы засчитываем попадание в остров, прибавляем единицу к счетчику и рекурсивно удаляем остров из матрицы.

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

Посмотреть решение в блоге

🅾️ Оценка сложности

По времени
Так как мы перебираем всю матрицу, то сложность перебора будет равна O(m*n). Также дополнительно может вызываться очистка острова, которая в худшем случае может занять O(m*n) операций (если вся матрица занята единицами.). Таким образом суммарная сложность O(2(m*n)), которая упрощается до O(m*n).

По памяти
O(1) — константная, так как мы выделяем дополнительную память только для хранения счетчиков.

#matrix #medium