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

Самый большой остров

средне

Дана карта в виде двумерного массива grid из 0 и 1, где 1 обозначает сушу, а 0 обозначает воду.

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

Нужно найти площадь самого большого острова в массиве. Если островов нет, верните 0. Площадь острова — это количество единиц в этом острове.

Пример 1:

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

Пример 2:

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

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

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

using System;
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 int Dfs(int i, int j, List<List<int>> grid, List<List<bool>> used)
    {
        // Если клетка выходит за границы, является водой или уже посещена, возвращаем 0
        if (!InBound(i, j, grid) || grid[i][j] == 0 || used[i][j])
        {
            return 0;
        }

        // Помечаем клетку как посещённую
        used[i][j] = true;
        int area = 1;

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

        return area;
    }

    // Основная функция для поиска площади самого большого острова
    public static int LargestIsland(List<List<int>> grid)
    {
        // Инициализация массива для отслеживания посещённых клеток
        List<List<bool>> used = new List<List<bool>>();
        for (int k = 0; k < grid.Count; k++)
        {
            used.Add(new List<bool>());
            for (int l = 0; l < grid[0].Count; l++)
            {
                used[k].Add(false);
            }
        }

        int maxArea = 0; // Переменная для хранения максимальной площади острова

        // Перебор всех клеток матрицы
        for (int i = 0; i < grid.Count; i++)
        {
            for (int j = 0; j < grid[i].Count; j++)
            {
                // Если клетка является сушей и ещё не посещена
                if (grid[i][j] == 1 && !used[i][j])
                {
                    // Вычисляем площадь текущего острова
                    int currentArea = Dfs(i, j, grid, used);
                    // Обновляем максимальную площадь
                    maxArea = Math.Max(maxArea, currentArea);
                }
            }
        }

        return maxArea;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

bool inBound(int i, int j, const vector<vector<int>>& grid) {
    return i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size();
}

int dfs(int i, int j, vector<vector<int>>& grid, vector<vector<bool>>& used) {
    if (!inBound(i, j, grid) || grid[i][j] == 0 || used[i][j]) {
        return 0;
    }

    used[i][j] = true;
    int area = 1;

    for (auto& direction : vector<vector<int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
        area += dfs(i + direction[0], j + direction[1], grid, used);
    }

    return area;
}

int largestIsland(vector<vector<int>>& grid) {
    vector<vector<bool>> used(grid.size(), vector<bool>(grid[0].size(), false));
    int maxArea = 0;

    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) {
            if (grid[i][j] == 1 && !used[i][j]) {
                int currentArea = dfs(i, j, grid, used);
                maxArea = max(maxArea, currentArea);
            }
        }
    }

    return maxArea;
}

package main

func inBound(i int, j int, grid [][]int) bool {
    return i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0])
}

func dfs(i int, j int, grid [][]int, used [][]bool) int {
    if !inBound(i, j, grid) || grid[i][j] == 0 || used[i][j] {
        return 0
    }

    used[i][j] = true
    area := 1

    for _, direction := range [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
        nextI, nextJ := i+direction[0], j+direction[1]
        area += dfs(nextI, nextJ, grid, used)
    }

    return area
}

func largestIsland(grid [][]int) int {
    used := make([][]bool, len(grid))
    for i := range used {
        used[i] = make([]bool, len(grid[0]))
    }
    maxArea := 0

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == 1 && !used[i][j] {
                currentArea := dfs(i, j, grid, used)
                if currentArea > maxArea {
                    maxArea = currentArea
                }
            }
        }
    }

    return maxArea
}

import java.util.*;

public class Solution {

    // Проверяет, находятся ли индексы i и j в пределах матрицы
    public 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) для подсчёта площади острова
    public static int dfs(int i, int j, List<List<Integer>> grid, List<List<Boolean>> used) {
        // Если клетка выходит за границы, является водой или уже посещена, возвращаем 0
        if (!inBound(i, j, grid) || grid.get(i).get(j) == 0 || used.get(i).get(j)) {
            return 0;
        }

        // Помечаем клетку как посещённую
        used.get(i).set(j, true);
        int area = 1;

        // Перебираем соседние клетки (вверх, вниз, влево, вправо)
        for (int[] direction : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
            area += dfs(i + direction[0], j + direction[1], grid, used);
        }

        return area;
    }

    // Основная функция для поиска площади самого большого острова
    public static int largestIsland(List<List<Integer>> grid) {
        // Инициализация массива для отслеживания посещённых клеток
        List<List<Boolean>> used = new ArrayList<>();
        for (List<Integer> row : grid) {
            List<Boolean> usedRow = new ArrayList<>();
            for (int k = 0; k < row.size(); k++) {
                usedRow.add(false);
            }
            used.add(usedRow);
        }

        int maxArea = 0; // Переменная для хранения максимальной площади острова

        // Перебор всех клеток матрицы
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(i).size(); j++) {
                // Если клетка является сушей и ещё не посещена
                if (grid.get(i).get(j) == 1 && !used.get(i).get(j)) {
                    // Вычисляем площадь текущего острова
                    int currentArea = dfs(i, j, grid, used);
                    // Обновляем максимальную площадь
                    maxArea = Math.max(maxArea, currentArea);
                }
            }
        }

        return maxArea;
    }
}

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]], used: List[List[bool]]) -> int:
    # Если клетка выходит за границы, является водой или уже посещена, возвращаем 0
    if not in_bound(i, j, grid) or grid[i][j] == 0 or used[i][j]:
        return 0
    
    # Помечаем клетку как посещённую
    used[i][j] = True
    
    # Площадь текущей клетки (1) + площадь всех соседних клеток
    area = 1
    # Перебираем соседние клетки (вверх, вниз, влево, вправо)
    for next_i, next_j in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
        area += dfs(next_i, next_j, grid, used)
    
    return area

def largest_island(grid: List[List[int]]) -> int:
    # Инициализация массива для отслеживания посещённых клеток
    used = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
    max_area = 0  # Переменная для хранения максимальной площади острова
    
    # Перебор всех клеток матрицы
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            # Если клетка является сушей и ещё не посещена
            if grid[i][j] == 1 and not used[i][j]:
                # Вычисляем площадь текущего острова
                current_area = dfs(i, j, grid, used)
                # Обновляем максимальную площадь
                max_area = max(max_area, current_area)
    
    return max_area

function inBound(i, j, grid) {
    return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
}

function dfs(i, j, grid, used) {
    if (!inBound(i, j, grid) || grid[i][j] === 0 || used[i][j]) {
        return 0;
    }

    used[i][j] = true;
    let area = 1;

    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (const [dx, dy] of directions) {
        area += dfs(i + dx, j + dy, grid, used);
    }

    return area;
}

export function largestIsland(grid) {
    const used = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(false));
    let maxArea = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1 && !used[i][j]) {
                const currentArea = dfs(i, j, grid, used);
                maxArea = Math.max(maxArea, currentArea);
            }
        }
    }

    return maxArea;
}

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

Время: O(n * m), где n кол-во строк и m кол-во столбцов входного массива.
Память: O(n * m), где n кол-во строк и m кол-во столбцов входного массива.