200. Number of Islands

Задача

Дана бинарная 2D сетка grid размером m x n , представляющая карту, где '1' — это суша, а '0' — вода. Верните количество островов.

Остров окружен водой и образован путем соединения соседних участков суши по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Примеры

Пример 1

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Пример 2

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Решение

Решение

/**
 * Временная сложность: O(M * N) — посещаем каждую ячейку максимум 1-2 раза
 * Пространственная сложность: O(M * N) — в худшем случае (весь грид это "1") глубина рекурсии равна M*N
 */
var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
 
    let count = 0;
    const rows = grid.length;
    const cols = grid[0].length;
 
    // Функция для "потопления" острова
    const sinkIsland = (r, c) => {
        // Проверка границ и того, является ли текущая ячейка сушей ('1')
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') {
            return;
        }
 
        // Превращаем сушу в воду, чтобы не посчитать её снова
        grid[r][c] = '0';
 
        // Рекурсивно проверяем всех соседей (верх, низ, лево, право)
        sinkIsland(r - 1, c);
        sinkIsland(r + 1, c);
        sinkIsland(r, c - 1);
        sinkIsland(r, c + 1);
    };
 
    // Проходим по всей сетке
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                sinkIsland(r, c); // Запускаем цепную реакцию
            }
        }
    }
 
    return count;
};

Решение 2 (BFS)

/**
 * Временная сложность: O(M * N)
 * Пространственная сложность: O(min(M, N)) — максимальный размер очереди
 */
var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
 
    let count = 0;
    const rows = grid.length;
    const cols = grid[0].length;
 
    // Вспомогательный массив сдвигов для соседей
    const directions = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
 
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                grid[r][c] = '0'; // Сразу топим стартовую точку
 
                // Запускаем BFS через очередь
                const queue = [
                    [r, c]
                ];
 
                while (queue.length > 0) {
                    const [curR, curC] = queue.shift(); // Берем первый элемент
 
                    for (const [dr, dc] of directions) {
                        const newR = curR + dr;
                        const newC = curC + dc;
 
                        // Если сосед в пределах границ и это суша
                        if (newR >= 0 && newR < rows &&
                            newC >= 0 && newC < cols &&
                            grid[newR][newC] === '1') {
 
                            grid[newR][newC] = '0'; // Топим соседа
                            queue.push([newR, newC]); // Добавляем в очередь для проверки его соседей
                        }
                    }
                }
            }
        }
    }
 
    return count;
};