Задача с собеседования в Яндекс

Дана прямоугольная матрица, заполненная нулями и единицами. Единицы это земля, нули это вода. Из каждой ячейки, заполненной 1, можно попасть в другую ячейку с 1, если каждая из их координат отличается не более, чем на единицу, т.е. каждая ячейка имеет до 8 соседей

Требуется найти количество таких "островов" в матрице

Решение:

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

Так как теперь их посчитать? Запускаем дфс из каждой единичной ячейки, если до этого она не посещалась, дфс обходит все вершинки из острова, отмечает их посещенными и увеличивает счетчик компонент связности, вот и всё.
Решение за O(NM)

@algoses