План курса / Все задачи / Алгоритмы и структуры данных

Число островов

средне

Дан двумерный массив grid размером m × n, где 1 — земля, 0 — вода. Остров — это соединённые по вертикали или горизонтали клетки с 1.

Нужно вернуть количество островов. grid разрешено изменять.

Пример 1:

Ввод: grid =
[1,1,0,0,0]
[1,1,0,0,0]
[0,0,0,0,0]
[0,0,0,1,1]
Вывод: 2

Пример 2:

Ввод: grid =
[1,1,1]
[0,1,0]
[1,1,1]
Вывод: 1

Ограничения:

0 <= grid[i][j] <= 1
1 <= m
1 <= n

public class Solution {
    // Проверяет, находятся ли индексы i и j в пределах матрицы
    private static bool InBound(int i, int j, List<List<int>> grid) {
        return i >= 0 && i < grid.Count && j >= 0 && j < grid[0].Count;
    }
    
    // Рекурсивный обход в глубину (DFS)
    private static void DFS(int i, int j, List<List<int>> grid) {
        // Если клетка выходит за границы или является водой, выходим
        if (!InBound(i, j, grid) || grid[i][j] == 0) {
            return;
        }
        // Помечаем клетку как воду, чтобы больше в нее не возвращаться
        grid[i][j] = 0;
        // Перебираем соседние клетки (вверх, вниз, влево, вправо)
        foreach (var (nextI, nextJ) in new[]{(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)}) {
            DFS(nextI, nextJ, grid);
        }
    }

    // Основная функция для подсчёта количества островов
    public static int IslandsIi(List<List<int>> grid) {
        if (grid == null || grid.Count == 0) {
            return 0;
        }

        // Считаем кол-во островов
        int islandCount = 0;
        for (int i = 0; i < grid.Count; i++) {
            for (int j = 0; j < grid[0].Count; j++) {
                if (grid[i][j] == 1) {
                    DFS(i, j, grid);
                    islandCount++;
                }
            }
        }

        return islandCount;
    }
}

#include <vector>
using namespace std;

// Проверяет, находятся ли индексы i и j в пределах матрицы
bool inBound(int i, int j, vector<vector<int>>& grid) {
    return 0 <= i && i < grid.size() && 0 <= j && j < grid[0].size();
}

// Рекурсивный обход в глубину (DFS)
void dfs(int i, int j, vector<vector<int>>& grid) {
    // Если клетка выходит за границы или является водой, выходим
    if (!inBound(i, j, grid) || grid[i][j] == 0) {
        return;
    }
    // Помечаем клетку как воду, чтобы больше в нее не возвращаться
    grid[i][j] = 0;
    // Перебираем соседние клетки (вверх, вниз, влево, вправо)
    for (auto [nextI, nextJ] : vector<pair<int, int>>{{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}}) {
        dfs(nextI, nextJ, grid);
    }
}

// Основная функция для подсчёта количества островов
int islandsIi(vector<vector<int>> grid) {
    if (grid.empty()) {
        return 0;
    }
    // Считаем кол-во островов
    int islandCount = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == 1) {
                dfs(i, j, grid);
                ++islandCount;
            }
        }
    }
    return islandCount;
}

package main

// Проверяет, находятся ли индексы i и j в пределах матрицы
func inBound(i, j int, grid [][]int) bool {
    return i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0])
}

// Рекурсивный обход в глубину (DFS)
func dfs(i, j int, grid [][]int) {
    // Если клетка выходит за границы или является водой, выходим
    if !inBound(i, j, grid) || grid[i][j] == 0 {
        return
    }
    // Помечаем клетку как воду, чтобы больше в нее не возвращаться
    grid[i][j] = 0
    // Перебираем соседние клетки (вверх, вниз, влево, вправо)
    directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    for _, dir := range directions {
        nextI, nextJ := i+dir[0], j+dir[1]
        dfs(nextI, nextJ, grid)
    }
}

// Основная функция для подсчёта количества островов
func islandsIi(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }
    // Считаем кол-во островов
    islandCount := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                dfs(i, j, grid)
                islandCount++
            }
        }
    }
    return islandCount
}

import java.util.*;

public class Solution {
    // Проверяет, находятся ли индексы i и j в пределах матрицы
    private boolean inBound(int i, int j, List<List<Integer>> grid) {
        return 0 <= i && i < grid.size() && 0 <= j && j < grid.get(0).size();
    }

    // Рекурсивный обход в глубину (DFS)
    private void dfs(int i, int j, List<List<Integer>> grid) {
        // Если клетка выходит за границы или является водой, выходим
        if (!inBound(i, j, grid) || grid.get(i).get(j) == 0) {
            return;
        }
        // Помечаем клетку как воду, чтобы больше в нее не возвращаться
        grid.get(i).set(j, 0);
        // Перебираем соседние клетки (вверх, вниз, влево, вправо)
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : directions) {
            dfs(i + dir[0], j + dir[1], grid);
        }
    }

    // Основная функция для подсчёта количества островов
    public Integer islandsIi(List<List<Integer>> grid) {
        if (grid == null || grid.isEmpty()) {
            return 0;
        }
        // Считаем кол-во островов
        int islandCount = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(0).size(); j++) {
                if (grid.get(i).get(j) == 1) {
                    dfs(i, j, grid);
                    islandCount++;
                }
            }
        }
        return islandCount;
    }
}

from typing import List

# Проверяет, находятся ли индексы i и j в пределах матрицы
def in_bound(i: int, j: int, grid: List[List[int]]) -> bool:
    return 0 <= i < len(grid) and 0 <= j < len(grid[0])

# Рекурсивный обход в глубину (DFS)
def dfs(i: int, j: int, grid: List[List[int]]) -> None:
    # Если клетка выходит за границы или является водой, выходим
    if not in_bound(i, j, grid) or grid[i][j] == 0:
        return
    # Помечаем клетку как воду, чтобы больше в нее не возвращаться
    grid[i][j] = 0
    # Перебираем соседние клетки (вверх, вниз, влево, вправо)
    for next_i, next_j in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
        dfs(next_i, next_j, grid)

# Основная функция для подсчёта количества островов
def islands_ii(grid: List[List[int]]) -> int:
    if not grid:
        return 0

    # Считаем кол-во островов
    island_count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                dfs(i, j, grid)
                island_count += 1

    return island_count

// Проверяет, находятся ли индексы i и j в пределах матрицы
function inBound(i, j, grid) {
    return 0 <= i && i < grid.length && 0 <= j && j < grid[0].length;
}

// Рекурсивный обход в глубину (DFS)
function dfs(i, j, grid) {
    // Если клетка выходит за границы или является водой, выходим
    if (!inBound(i, j, grid) || grid[i][j] === 0) return;
    // Помечаем клетку как воду, чтобы больше в нее не возвращаться
    grid[i][j] = 0;
    // Перебираем соседние клетки (вверх, вниз, влево, вправо)
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (const [di, dj] of directions) {
        dfs(i + di, j + dj, grid);
    }
}

/**
 * Основная функция для подсчёта количества островов
 * @param {number[][]} grid
 * @returns {number}
 */
export function islandsIi(grid) {
    if (!grid || grid.length === 0) return 0;
    // Считаем кол-во островов
    let islandCount = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1) {
                dfs(i, j, grid);
                islandCount++;
            }
        }
    }
    return islandCount;
}

Оценка сложности

Время: O(n*m), где n - размер grid
Память: O(n*m)

Память O(n*m) из-за рекурсии, которая тратит память на стеке.