Решение задачи с leetcode Python.

Задача. Количество изолированных островов

https://leetcode.com/problems/number-of-closed-islands/

@python_job_interview – python вопросы с собеседований

Условие задачи: дан двумерный массив, содержащий 0 (острова) и 1(воду). 

Остров – множество нулей, соединенных в четырех направлениях (справа, снизу, слева, сверху), изолированый остров – множество нулей, окруженных со всех сторон единицами. 

Надо посчитать количество изолированных островов. 

Пример:

Ввод: 

grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

Вывод: 2

Объяснение:

Ввод: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]

Вывод: 1

Решение

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