Аралдың максималды ауданы


Күрделілік дәрежесі орта
Жиі кіреді Amazon Bloomberg DoorDash Facebook Google Oracle Palantir Technologies
Array Бірінші іздеу Тереңдікті бірінші іздеу Графика Matrix

Ақаулықтың сипаттамасы: 2D матрицасын ескере отырып, матрицада тек 0 (суды білдіретін) және 1 (жерді бейнелейтін) жазбалар болады. Матрицадағы арал барлық көршілес 1-ді 4 бағытта (көлденең және тік) біріктіру арқылы құрылады. Аралдың максималды ауданын табыңыз Матрица. Тордың барлық төрт шеті сумен қоршалған деп есептейік.

Ескерту: Арал тобының ауданы - бұл сол арал тобындағы ұяшықтардың саны.

мысал

Input 1: 
Grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,1,1,1,0,0,0}, 
        {0,1,1,0,1,0,0,0,0,1,0,0,0}, 
        {0,1,0,0,1,1,0,0,1,0,1,0,0}, 
        {0,1,0,0,1,1,0,0,1,1,1,0,0}, 
        {0,0,0,0,0,0,0,0,1,0,1,0,0}, 
        {0,0,0,0,0,0,0,1,1,1,0,0,0}, 
        {0,0,0,0,0,0,0,1,1,0,0,0,0}}

Output: Area of largest island = 12 


Input 2: 
Grid = {{0,1,0,0,1,1,0}, 
        {0,0,0,0,1,0,0}, 
        {0,0,0,1,1,0,0}, 
        {0,0,1,1,0,0,0}}

Output: Area of largest island = 7

Жоғарыда келтірілген алғашқы мысалды қарастырайық. Төменде жоғарыда көрсетілген 2D тордың бейнесі келтірілген, жерді көрсететін ұяшықтар 1 деп белгіленеді (жасыл түске боялған), ал суды көрсететін ұяшықтар 0 деп белгіленеді (көк түске боялған).

Аралдың максималды ауданы

Диаграммадан байқағандай 5 арал тобы құрылады. Ең үлкен арал тобы қызылмен, ал кішігірім арал топтары сары түспен көрсетілген. Ең үлкен арал тобының ауданы 12 бірлікті құрайды.

Аралдың максималды ауданы

Ескерту: арал топтары тор ұяшықтарын көлденең (оңға және солға) және тік (жоғары және төмен) бағыттарда (диагональды бағыттарда емес) қосу арқылы қалыптасатындығын ескеру қажет.

Аралдың максималды ауданы үшін шешім түрлері

  1. Тереңдікті бірінші іздеу
  2. Бірінші іздеу

Тереңдікті бірінші іздеу

Аралдың максималды аумағына көзқарас

Біз ең үлкен аралдың аумағын 1-ден тұратын ұяшықтардың барлық көршілеріне (және осы көршілердің көршілеріне) бару арқылы есептеуді мақсат етеміз, бұл көршілер мен көршілердің көршілеріне рекурсивті траверсті орындау арқылы жүзеге асырылады. DFS. DFS-ні орындау кезінде біз кірген барлық жаңа ұяшықтар үшін (тек 1-ден тұратын) жалпы кіретін аумақты 1-ге көбейтеміз.

Аралдың максималды ауданы алгоритмі

  1. 2 өлшемді торды айналып өтіңіз және құрамында 1 бар ұяшықтардың әрқайсысынан DFS өтпесін орындаңыз.
  2. Ағымдағы ұяшықты ұяшық мәнін 0-ге өзгерту арқылы барған ретінде белгілеңіз.
  3. Ағымдағы ұяшықтан басталатын аралдың ауданы - 1.
  4. 1-ден тұратын ағымдағы ұяшықтардың барлық көршілеріне (жоғарыдан оңға-солға) рекурсивті түрде барыңыз, осы көршілерді кірген деп белгілеңіз, сонымен қатар кірген әрбір жарамды көршінің (мәні 1 бар ұяшықтардың) аумағын 1-ге көбейтіңіз (ұяшық мәнін өзгерту арқылы) 0-ге дейін).
  5. Өткеннен кейін алынған аумақты толық қайтарыңыз.
  6. 2,3,4-ден тұратын ұяшықтардың әрқайсысына (матрицаның) 5 және 1 қадамдарын орындаңыз және алынған барлық аймақ мәндерінің максимумын қайтарыңыз.

Жоғарыда келтірілген мысал торын қарастырайық: біз ең үлкен аралдың ең жоғарғы және ең жоғарғы ұяшығынан бастаймыз, оның мәні 1-ге тең (қазіргі уақытта осы ұяшықтың үстіндегі және сол жақтағы барлық ұяшықтары кіріп үлгерген) және DFS травералын орындаймыз.

DFS травералы белгілі бір бағытта мүмкін болатын ең үлкен тереңдікке дейін ұяшықтарға барады. Белгілі бір ұяшықтан басталатын қозғалыс бағыты келесі ретпен: жоғарыдан оңға - солға. DFS өтуі алгоритм ең үлкен аралдың ең жоғарғы және сол жақ ұяшығынан төменде бейнеленген:

Ең үлкен аралға барған ұяшықтар рад деп белгіленді.

Аралдың максималды ауданы

Аралдың максималды ауданы

Аралдың максималды ауданы

Аралдың максималды ауданы

Аралдың максималды ауданы

Байқағанымыздай, жүру кезінде өткен жасушалар саны - 12. Сондықтан ең үлкен аралдың ауданы - 12.

Іске асыру

C ++ бағдарламасы
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to perform DFS in four directions(up-right-down-left)
int dfs(vector<vector<int>>& grid, int row, int col) 
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* since the current cell has value = 1
        minimum area we start with is 1*/
    int area = 1;
    
    /* since you have already visited the current cell
    mark it as already visited */
    grid[row][col] = 0;
    
    /* used for traversing in four directions(up-right-down-left)*/
    vector<int> dir({-1,0,1,0,-1});
    
    /* we begin our traversal into four directions from the current cell*/
    for (int i = 0; i < 4; i++) 
    {
        int r = row+dir[i], c = col+dir[i+1];
        
        /* make traversals only when next cell lies within the matrix and is unvisited*/
        if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
            area += dfs(grid, r, c);
    }
    /* total number of cells with value 1 visited from the current cell */
    return area;
}

/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* stores the area of largest consecutive 1's*/
    int maxArea = 0;
    
    /* visit each cell of the matrix*/
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
        /* begin your traversal from the cell which has value as 1(land)*/
            if (grid[i][j] == 1) 
            /* store the largest area*/
            maxArea = max(maxArea, dfs(grid, i, j));
            
    return maxArea;    
}

/* main function to implement above function */
int main()
{
    vector<vector<int>> grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,1,1,0,1,0,0,0,0,1,0,0,0},
                                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                                {0,0,0,0,0,0,0,0,1,0,1,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
    
    cout<<"Area of largest island = "<<largestIsland(grid);
    
    return 0;
}
Area of largest island = 12
Java бағдарламасы
import java.util.*;
import java.io.*;

class tutorialCup
{
    // function to perform DFS in four directions(up-right-down-left)
    static int dfs(int grid[][], int row, int col) 
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* since the current cell has value = 1
            minimum area we start with is 1*/
        int area = 1;
        
        /* since you have already visited the current cell
        mark it as already visited */
        grid[row][col] = 0;
        
        /* used for traversing in four directions(up-right-down-left)*/
        int [] dir = {-1,0,1,0,-1};
        
        /* we begin our traversal into four directions from the current cell*/
        for (int i = 0; i < 4; i++) 
        {
            int r = row+dir[i], c = col+dir[i+1];
            
            /* make traversals only when next cell lies within the matrix and is unvisited*/
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
                area += dfs(grid, r, c);
        }
        /* total number of cells with value 1 visited from the current cell */
        return area;
    }

    
    /* function that returns area of largest island */
    static int largestIsland(int grid[][])
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* stores the area of largest consecutive 1's*/
        int maxArea = 0;
        
        /* visit each cell of the matrix*/
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
            /* begin your traversal from the cell which has value as 1(land)*/
                if (grid[i][j] == 1) 
                /* store the largest area*/
                maxArea = Math.max(maxArea, dfs(grid, i, j));
                
        return maxArea;    
    }
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        int grid[][] =  {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,1,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,1,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
        System.out.print("Area of largest island = "+largestIsland(grid)); 
    }
}
Area of largest island = 12

Аралдың максималды ауданы бойынша кешенділікті талдау

  1. Уақыттың күрделілігі: T (n) = O (R * C), біз матрицаның әр ұяшығын дәл бір рет айналып өтеміз.
  2. Кеңістіктің күрделілігі: A (n) = O (R * C), өйткені біз белгілі бір ұяшыққа кірген-кірмегенін бақылайтын басқа матрицалық кеңістікті пайдаланбағандықтан, тор көздерін барған ұяшықтар белгіленетін етіп өзгертеміз. барғанындай.

Бірінші іздеу

Аралдың максималды аумағына көзқарас

Біз ең үлкен аралдың аумағын 1-ден тұратын клеткалардың барлық көршілеріне (және осы көршілердің көршілеріне) бару арқылы есептеуді мақсат етеміз, бұл көршілер мен көршілердің көршілеріне қайталанатын өтпелілік BFS орындау арқылы жүзеге асырылады. BFS-ті қолданған кезде, біз кірген әрбір жаңа ұяшыққа (тек 1-ден тұратын) баратын жалпы аумақты 1-ге көбейтеміз.

Аралдың максималды ауданы алгоритмі

  1. 2 өлшемді торды кесіп өтіңіз және құрамында 1 бар ұяшықтардың әрқайсысынан BFS травералын орындаңыз.
  2. Ағымдағы ұяшықты ұяшық мәнін 0-ге өзгерту арқылы барған ретінде белгілеңіз.
  3. Ағымдағы ұяшықтан басталатын аралдың ауданы - 1.
  4. Құрамында 1 бар ағымдағы ұяшықтардың барлық көршілеріне (жоғарыдан оңға-солға) барыңыз, осы көршілерді барған деп белгілеңіз, сонымен қатар әрбір жарамды көршінің (мәні 1 бар ұяшықтардың) аумағын 1-ге ұлғайтыңыз (ұяшық мәнін өзгерту арқылы) 0-ге дейін).
  5. Өткеннен кейін алынған аумақты толық қайтарыңыз.
  6. 2,3,4-ден тұратын ұяшықтардың әрқайсысына (матрицаның) 5 және 1 қадамдарын орындаңыз және алынған барлық аймақ мәндерінің максимумын қайтарыңыз.

Жоғарыда келтірілген мысал торын қарастырайық: біз ең үлкен аралдың 1 мәні бар ең сол жақ және ең жоғарғы ұяшығынан бастаймыз (қазіргі уақытта осы ұяшықтың үстіндегі және сол жағындағы барлық ұяшықтар кіріп үлгерген) және BFS травералын орындаймыз.

BFS траверсалы алдымен белгілі бір ұяшықтың барлық көршілес ұяшықтарына (жоғарыдан оңға - солға) барады, содан кейін қайталанатын түрде осы көршілердің көршілеріне барады. Төменде ең үлкен аралдың ең жоғарғы және сол жақ ұяшығындағы BFS траекториялық алгоритмі көрсетілген:

Ең үлкен аралға барған ұяшықтар қызыл деп белгіленді.

Байқағанымыздай, жүру кезінде өткен жасушалар саны - 12. Сондықтан ең үлкен аралдың ауданы - 12.

Іске асыру

C ++ бағдарламасы
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to perform BFS in four directions(up-right-down-left)
int bfs(vector<vector<int>>& grid, int row, int col) 
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* since the current cell has value = 1
            minimum area we start with is 1*/
    int area = 1;
    
    /* create a queue to be used in BFS*/
    queue<pair<int,int>> q;
    /* push the current cell */
    q.push({row, col});
    
    /* since you have already visited the current cell
        mark it as already visited */
    grid[row][col] = 0;
    /* used for traversing in four directions(up-right-down-left)*/
    vector<int> dir({-1,0,1,0,-1});
    
    /* begin BFS traversal */
    while (!q.empty()) 
    {
        /* pop a cell with containing 1(land) */
        int y = q.front().first, x = q.front().second;
        q.pop();
        
        /* we begin our traversal into four directions from the current cell*/
        for (int i = 0; i < 4; i++) 
        {
            int r = y+dir[i], c = x+dir[i+1];
            /* make traversals only when next cell lies within the matrix and is unvisited*/
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
            {
                /* mark next cell as visited, increase the visited area and push next cells into the queue*/
                grid[r][c] = 0;
                area++;
                q.push({r,c});
            }
        }
    }
    /* total number of cells with value 1 visited from the current cell */
    return area;
}
/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* stores the area of largest consecutive 1's*/
    int maxArea = 0;
    
    /* visit each cell of the matrix*/
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
        /* begin your traversal from the cell which has value as 1(land)*/
            if (grid[i][j] == 1) 
            /* store the largest area*/
            maxArea = max(maxArea, bfs(grid, i, j));
            
    return maxArea;    
}

/* main function to implement above function */
int main()
{
    vector<vector<int>> grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,1,1,0,1,0,0,0,0,1,0,0,0},
                                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                                {0,0,0,0,0,0,0,0,1,0,1,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
    
    cout<<"Area of largest island = "<<largestIsland(grid);   
    return 0;
}
Area of largest island = 12
Java бағдарламасы
import java.util.*;
import java.io.*;

class tutorialCup
{
    /* define pair class to handle 2D co-ordinates in a matrix*/
    static class pair
    {
        int row;
        int col;
        
        pair(int y,int x)
        {
            row = y;
            col = x;
        }
    }
    // function to perform DFS in four directions(up-right-down-left)
    static int dfs(int grid[][], int row, int col) 
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* since the current cell has value = 1
                minimum area we start with is 1*/
        int area = 1;
        
        /* create a queue to be used in BFS*/
        Queue<pair> q = new LinkedList<pair>();
        /* push the current cell */
        q.add(new pair(row, col));
        
        /* since you have already visited the current cell
            mark it as already visited */
        grid[row][col] = 0;
        /* used for traversing in four directions(up-right-down-left)*/
        int [] dir = {-1,0,1,0,-1};
        
        /* begin BFS traversal */
        while (!q.isEmpty()) 
        {
            /* pop a cell with containing 1(land) */
            pair p = q.remove();
            int y = p.row, x = p.col;
            
            /* we begin our traversal into four directions from the current cell*/
            for (int i = 0; i < 4; i++) 
            {
                int r = y+dir[i], c = x+dir[i+1];
                /* make traversals only when next cell lies within the matrix and is unvisited*/
                if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
                {
                    /* mark next cell as visited, increase the visited area and push next cells into the queue*/
                    grid[r][c] = 0;
                    area++;
                    q.add(new pair(r,c));
                }
            }
        }
        /* total number of cells with value 1 visited from the current cell */
        return area;
    }

    
    /* function that returns area of largest island */
    static int largestIsland(int grid[][])
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* stores the area of largest consecutive 1's*/
        int maxArea = 0;
        
        /* visit each cell of the matrix*/
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
            /* begin your traversal from the cell which has value as 1(land)*/
                if (grid[i][j] == 1) 
                /* store the largest area*/
                maxArea = Math.max(maxArea, dfs(grid, i, j));
                
        return maxArea;    
    }
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        int grid[][] =  {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,1,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,1,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
        System.out.print("Area of largest island = "+largestIsland(grid)); 
    }
}
Area of largest island = 12

Аралдың максималды ауданы бойынша кешенділікті талдау

  1. Уақыттың күрделілігі: T (n) = O (R * C), біз матрицаның әр ұяшығын дәл бір рет айналып өтеміз.
  2. Кеңістіктің күрделілігі: A (n) = O (R * C). біз белгілі бір ұяшыққа кірген-кірмегендігімізді қадағалайтын басқа матрицалық кеңістікті пайдаланбағандықтан, тор көздерін кірген ұяшықтар кірген деп белгіленетін етіп өзгертеміз.

Әдебиеттер тізімі