Условие

Количество связанных областей в матрице (Number of Connected Regions)

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

Напишите функцию, которая возвращает количество таких связанных областей в матрице.

Входные данные Двумерный массив целых чисел grid (матрица размером m×n).

Выходные данные Целое число — количество связанных областей.

Ограничения 1 <= m, n <= 100

Код для заполнения:

Доступно без импорта: json, sys, io

def count_regions(grid): # TODO: напишите решение здесь return 0

Ответ

Обойдите матрицу: каждая ещё не посещённая ячейка начинает новую область. Flood fill отмечает всех её соседей с тем же значением; диагонали не учитываются.

def count_regions(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    regions = 0
    for r in range(rows):
        for c in range(cols):
            if (r, c) in seen:
                continue
            regions += 1
            seen.add((r, c))
            stack = [(r, c)]
            value = grid[r][c]
            while stack:
                x, y = stack.pop()
                for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                    if (0 <= nx < rows and 0 <= ny < cols
                            and (nx, ny) not in seen and grid[nx][ny] == value):
                        seen.add((nx, ny))
                        stack.append((nx, ny))
    return regions

Каждая ячейка посещается один раз: O(mn) времени и памяти. Итеративный стек не упирается в лимит глубины рекурсии Python. Входная матрица не изменяется.