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

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

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

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

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

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

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

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

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

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

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

Написать комментарий

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

Декодировка строки

Апрель 30, 2023 г.

Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными. Чтобы выработать решение, рассмотрим пример: [crayon-673efb11170c4266494272/] ...

Читать

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи. Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов. ...

Читать

 

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

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



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