Задача — число островов

Разбираю задачу #200 с литкода, число островов (number of islands).

Задан двумерный массив, в котором участки суши помечены как «1», а участки воды — как «0». Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют единый остров, только если соединяются напрямую по X или по Y (т.е. по диагонали они не соединяются).

Этот вид задач, я отношу к задачам на сегментацию данных, т.к. нам нужно сгруппировать участки суши по заданному признаку.

Изначально не ясно сколько получится островов, а также есть ли в массиве участки суши вообще.

Чтобы понять алгоритм, рассмотрим следующий пример набора данных.

Отчетливо видно, что у нас два острова. Но мы это видим, потому что можем анализировать такой небольшой массив как единое целое.

Программа же (если конечно это не нейросеть), должна найти для начала хоть какой то участок суши. Это даст нам определенность, что у нас есть как минимум 1 остров. Мы отметим найденный участок номером острова, и двигаясь к соседним участкам, будем помечать их тем же самым номером острова.

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

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

Если в целом алгоритм ясен, перейдем к деталям, разбирая код (typescript):

Мало букафф? Читайте есчо !

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать

GreyCode генератор

Май 3, 2023 г.

Задачи с бинарными последовательностями мне очень нравятся из-за их "эвристичности". Решение часто скрывается в двух шагах, но додуматься не просто. Следующая задача описывается так - нужно сгенерировать n-разрядный "серый код". Если вы не ...

Читать

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

Результат k-ой перестановки

Июль 5, 2023 г.

Очередная задача с литкода (№60. Permutation Sequence). В общем случае формулируется так: дан набор элементов, требуется вернуть этот набор после k перестановок. ...

Читать
 

Комментарии к «Задача — число островов»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: