Подсчёт островов

Решение: Подсчёт Островов на Карте

Эта классическая задача на поиск связных компонентов в графе. Нужно подсчитать количество групп соединённых единиц в двумерном массиве, используя поиск в глубину (DFS) или ширину (BFS).

Подход 1: DFS (Глубина)

Используем рекурсивный поиск в глубину для исследования каждого острова:

def num_islands(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
            return
        
        grid[r][c] = 0  # Помечаем как посещённую
        
        # Проверяем все 4 направления
        dfs(r + 1, c)  # Вниз
        dfs(r - 1, c)  # Вверх
        dfs(r, c + 1)  # Вправо
        dfs(r, c - 1)  # Влево
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                islands += 1
                dfs(r, c)
    
    return islands

Сложность:

• Временная: O(m * n)
• Пространственная: O(m * n) из-за стека рекурсии

Подход 2: BFS (Ширина)

Итеративный поиск в ширину с использованием очереди:

from collections import deque

def num_islands(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def bfs(r: int, c: int) -> None:
        queue = deque([(r, c)])
        grid[r][c] = 0
        
        while queue:
            r, c = queue.popleft()
            
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 0
                    queue.append((nr, nc))
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                islands += 1
                bfs(r, c)
    
    return islands

Сложность:

• Временная: O(m * n)
• Пространственная: O(min(m, n)) для очереди

Подход 3: Union-Find (DSU)

Используем структуру данных «Система непересекающихся множеств»:

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def num_islands(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    islands = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                islands += 1
                # Объединяем с соседними единицами
                if r + 1 < rows and grid[r + 1][c] == 1:
                    if uf.union(r * cols + c, (r + 1) * cols + c):
                        islands -= 1
                if c + 1 < cols and grid[r][c + 1] == 1:
                    if uf.union(r * cols + c, r * cols + c + 1):
                        islands -= 1
    
    return islands

Сложность: O(m * n * α(m * n)), где α — обратная функция Аккермана

Пример

grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
]
print(num_islands(grid))  # → 3

Рекомендация

Для собеседования используй подход 1 (DFS) — простой и интуитивный. Если попросят оптимизацию памяти, предложи BFS. Union-Find используется реже, но показывает продвинутые навыки.