UniLecs #Task. Islands
Задача: дана карта островов, которая представлена в виде матрицы NxM, состоящую только из 1 (суша) и 0 (вода). Вам необходимо посчитать кол-во островов на этой карте.
Примечание: будем считать, что остров окружен водой и образован соединением соседних земель по горизонтали и вертикали.
Входные данные: matrix — матрица NxM, состоящая из 1 и 0, где 1 <= N*M <= 10⁵.
Вывод: кол-во островов на карте.
Примеры:
Разбор
Один из классических подходов в решении таких задач это поиск в глубину.
Проходим по матрице и для каждого узла “1” запускаем поиск в глубину, который изменяет состояние каждого посещенного узла в “0”. Тогда при каждом запуске поиска в глубину для корневого узла будем увеличивать счетчик, ктр и будет содержать кол-во островов на карте.
В функции поиска в глубину рекурсивно будем запускать функцию вправо/влево и вверх/вниз. Детали реализации смотрите ниже!
Реализация
https://gist.github.com/unilecs/6e30b64c033d2ff21f549086c4625c21
