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

Острова

легко

Дана карта в виде двумерного массива grid, где 1 обозначает сушу, а 0 обозначает воду. Нужно определить, сколько отдельных островов есть на карте.

Островом считается группа соединённых по вертикали или горизонтали клеток с сушей (1), при этом ни одна из клеток острова не должна соприкасаться с краем карты — то есть такие острова полностью окружены водой и не касаются границ массива.

Замечание: при необходимости, можно изменять исходный массив.

Пример 1:

Ввод: grid =
[[1,0,0]
,[1,1,0]
,[1,1,1]
,[1,0,0]]
Вывод: 0
Объяснение: на карте есть один участок суши, но мы не считаем его островом, потому что он прилегает к краевым элементам карты.

Пример 2:

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

Пример 3:

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

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

len(grid) >= 1
len(grid[i]) >= 1

using System.Collections.Generic;

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

    // Рекурсивный обход в глубину (DFS) для удаления суши, прилегающей к границам
    public 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;

        // Перебираем соседние клетки (вниз, вверх, вправо, влево)
        var directions = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
        foreach (var dir in directions)
        {
            Dfs(i + dir.Item1, j + dir.Item2, grid);
        }
    }

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

        // Удаляем сушу, прилегающую к границам карты
        for (int i = 0; i < grid.Count; i++)
        {
            for (int j = 0; j < grid[0].Count; j++)
            {
                if ((i == 0 || i == grid.Count - 1 || j == 0 || j == grid[0].Count - 1) && grid[i][j] == 1)
                {
                    Dfs(i, j, grid);
                }
            }
        }

        // Считаем количество оставшихся островов
        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, const vector<vector<int>>& grid) {
    return i >= 0 && i < grid.size() && j >= 0 && 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 (const auto& next : vector<vector<int>>{{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}}) {
        dfs(next[0], next[1], grid);
    }
}

// Основная функция для подсчета количества островов
int numIslands(vector<vector<int>>& grid) {
    if (grid.empty()) {
        return 0;
    }

    // Удаляем сушу, прилегающую к границам карты
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if ((i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1) && grid[i][j] == 1) {
                dfs(i, j, grid);
            }
        }
    }

    // Считаем количество оставшихся островов
    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
    // Перебираем соседние клетки (вниз, вверх, вправо, влево)
    for _, next := range [][2]int{{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}} {
        dfs(next[0], next[1], grid)
    }
}

// Основная функция для подсчета количества островов
func numIslands(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }

    // Удаляем сушу, прилегающую к границам карты
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if (i == 0 || i == len(grid)-1 || j == 0 || j == len(grid[0])-1) && grid[i][j] == 1 {
                dfs(i, j, grid)
            }
        }
    }

    // Считаем количество оставшихся островов
    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.List;

public class Solution {

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

    // Рекурсивный обход в глубину (DFS) для удаления суши, прилегающей к границам
    private static 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 static int numIslands(List<List<Integer>> grid) {
        if (grid.isEmpty()) return 0;

        // Удаляем сушу, прилегающую к границам карты
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(0).size(); j++) {
                if ((i == 0 || i == grid.size() - 1 || j == 0 || j == grid.get(0).size() - 1) && grid.get(i).get(j) == 1) {
                    dfs(i, j, grid);
                }
            }
        }

        // Считаем количество оставшихся островов
        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 num_islands(grid: List[List[int]]) -> int:
    if not grid:
        return 0

    # Удаляем сушу, прилегающую к границам карты
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            # Если клетка находится на границе и является сушей
            if (i == 0 or i == len(grid) - 1 or j == 0 or j == len(grid[0]) - 1) and grid[i][j] == 1:
                dfs(i, j, grid)

    # Считаем количество оставшихся островов
    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 i >= 0 && i < grid.length && j >= 0 && 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 dir of directions) {
        dfs(i + dir[0], j + dir[1], grid);
    }
}

// Основная функция для подсчета количества островов
export function numIslands(grid) {
    if (grid.length === 0) return 0;

    // Удаляем сушу, прилегающую к границам карты
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if ((i === 0 || i === grid.length - 1 || j === 0 || j === grid[0].length - 1) && grid[i][j] === 1) {
                dfs(i, j, grid);
            }
        }
    }

    // Считаем количество оставшихся островов
    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 кол-во строк и m кол-во столбцов входного массива.
Память: O(n * m), где n кол-во строк и m кол-во столбцов входного массива.