Подсчёт количества островов в двумерной решётке

Условие

Дан двумерный массив из символов '1' (земля) и '0' (вода) размеров m × n, представляющий карту. Требуется вернуть число островов. Остров — это группа смежных по вертикали или горизонтали ячеек с символом '1', полностью окружённая ячейками '0'. Считается, что внешние границы карты тоже окружены водой.

Пример 1: Вход: map = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Вывод: 1

Пример 2: Вход: map = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Вывод: 3

Ответ

Обойдите все клетки. Каждая ещё не посещённая единица начинает новый остров; обход DFS или BFS помечает все связанные с ней единицы, чтобы не считать их повторно.

Короткая реализация на Python с явным стеком изменяет карту на месте:

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            grid[r][c] = '0'
            stack = [(r, c)]
            while stack:
                x, y = stack.pop()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    a, b = x + dx, y + dy
                    if 0 <= a < rows and 0 <= b < cols and grid[a][b] == '1':
                        grid[a][b] = '0'
                        stack.append((a, b))
    return count

Для прямоугольной карты время O(mn), дополнительная память в худшем случае O(mn). Если исходную карту менять нельзя, используйте отдельную таблицу посещения. Диагональные касания не объединяют острова.