Number of Islands

Карта представлена списком строк одинаковой длины. Каждый символ — это либо 1, участок суши, либо 0, участок воды. Два участка суши принадлежат одному острову, если один находится непосредственно выше, ниже, левее или правее другого. Участки, соприкасающиеся только углами, не связаны.

Рассмотрим карту ["11000", "11000", "00100", "00011"]:

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

Итак, на карте 3 острова.

На самом деле карта представляет собой граф: каждый участок суши — это узел, а ребро соединяет два участка суши, имеющих общую сторону. Подсчёт островов означает подсчёт связных компонент этого графа. Каждый раз, когда вы находите ещё не посещённый участок суши, вы обнаруживаете новый остров и исследуете его целиком, прежде чем двигаться дальше.

Напиши функцию с именем numIslands, которая получает grid — список строк, состоящих из 1 (суша) и 0 (вода), и возвращает количество островов. Остров — это группа клеток суши, соединённых вверх, вниз, влево или вправо.

Например, ["01110", "01000", "00011", "11001"] возвращает 3: фигуру в верхних строках, группу справа и пару в нижнем левом углу.

Ограничения: 1 <= количество строк, количество столбцов <= 150. Все строки имеют одинаковую длину.