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

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

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

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

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

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

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

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

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

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

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

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

Задача: подсчитать варианты размена монет

Август 11, 2023 г.

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

Читать

TS: функция преобразования к каноническому пути

Март 15, 2023 г.

Увидел эту задачу на leetcode - https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS. Задача ...

Читать

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

Март 13, 2023 г.

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

Читать

Задача о неперекрывающихся интервалах

Июнь 7, 2023 г.

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

Читать
 

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

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



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