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

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

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

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

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

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

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

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

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

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

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

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

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

87. Scramble string - задача о перетасованных строках

Март 30, 2023 г.

Решаем задачу с литкода о перетасовке строки. Даны две строки, нужно определить является ли вторая строка результатом перетасовки букв в первой. Правила ...

Читать

Задача группировки подобных строк

Апрель 28, 2023 г.

Речь идет о № 839 с leetcode. Формулируется проблема таким образом - дан массив строк, которые отличаются (или не отличаются) друг от друга перестановкой ...

Читать

 

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

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



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