द्वीप का अधिकतम क्षेत्र


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना ब्लूमबर्ग DoorDash Facebook गूगल ओरेकल पलांटिर टेक्नोलॉजीज
ऐरे पहले चौड़ाई खोजो गहराई पहली खोज ग्राफ मैट्रिक्स

समस्या का विवरण: 2 डी मैट्रिक्स को देखते हुए, मैट्रिक्स में प्रविष्टियों के रूप में केवल 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

ऊपर दिए गए पहले इनपुट उदाहरण पर विचार करें। नीचे दिए गए 2 डी ग्रिड का प्रतिनिधित्व है, भूमि का प्रतिनिधित्व करने वाली कोशिकाओं को 1 के रूप में चिह्नित किया जाता है (हरे रंग के रूप में) और पानी का प्रतिनिधित्व करने वाली कोशिकाओं को 0 (नीले रंग में रंगा हुआ) के रूप में चिह्नित किया जाता है।

द्वीप का अधिकतम क्षेत्र

जैसा कि आरेख से देखा गया है, 5 द्वीप समूह बनते हैं। सबसे बड़े द्वीप समूह को लाल रंग में रेखांकित किया गया है जबकि छोटे द्वीप समूह को पीले रंग में रेखांकित किया गया है। सबसे बड़े द्वीप समूह का क्षेत्रफल 12 इकाई है।

द्वीप का अधिकतम क्षेत्र

नोट: यह ध्यान दिया जाना चाहिए कि द्वीप समूह क्षैतिज (दाएं और बाएं) और ऊर्ध्वाधर (ऊपर और नीचे) दिशाओं (और विकर्ण दिशाओं में नहीं) में ग्रिड कोशिकाओं को जोड़कर बनते हैं।

द्वीप के मैक्स क्षेत्र के लिए समाधान के प्रकार

  1. गहराई पहली खोज
  2. पहले चौड़ाई खोजो

गहराई पहली खोज

द्वीप के अधिकतम क्षेत्र के लिए दृष्टिकोण

हम पुनरावर्ती सभी कोशिकाओं के पड़ोसियों (और इन पड़ोसियों के पड़ोसियों) पर जाकर सबसे बड़े द्वीप के क्षेत्र की गणना करना चाहते हैं, जिनमें 1. पड़ोसी और पड़ोसियों के पड़ोसियों के लिए यह पुनरावर्ती ट्रैवर्स प्रदर्शन करके हासिल किया जाता है डीएफएस। डीएफएस का प्रदर्शन करते समय हमने प्रत्येक नए सेल (जिसमें केवल 1 का दौरा किया है) के लिए 1 द्वारा दौरा किए गए कुल क्षेत्र को पुन: बढ़ाता है।

द्वीप के अधिकतम क्षेत्र के लिए एल्गोरिथ्म

  1. 2 डी युक्त प्रत्येक सेल से 1 डी ग्रिड का प्रदर्शन डीएफएस ट्रैवर्सल करें।
  2. सेल वैल्यू को 0 में बदलकर वर्तमान सेल को चिह्नित करें।
  3. वर्तमान सेल से शुरू होने वाले द्वीप का क्षेत्रफल 1 है।
  4. वर्तमान में मौजूद सभी कक्षों के सभी पड़ोसियों (ऊपर-दाएं-नीचे-बाएं) पर जाएँ, इन पड़ोसियों को विज़िट के रूप में चिह्नित करें, और प्रत्येक मान्य पड़ोसी (मान 1 के साथ कक्ष) पर गए सेल मान को बदलकर क्षेत्र को 1 से बढ़ाएं। ०)।
  5. ट्रैवर्सल के पूर्ण होने के बाद प्राप्त क्षेत्र वापस आ जाता है।
  6. 2,3,4 (युक्त मैट्रिक्स) में से प्रत्येक के लिए चरण 5 और 1 को निष्पादित करें और प्राप्त किए गए सभी क्षेत्र मानों की अधिकतम वापसी करें।

ऊपर दिए गए उदाहरण ग्रिड पर विचार करें: हम सबसे बड़े द्वीप के बाएं-सबसे और शीर्ष-सबसे सेल से शुरू करते हैं जिसका मूल्य 1 है (अब तक, इस सेल के ऊपर और बाएं सभी सेल पहले ही देखे जा चुके हैं) और डीएफएस ट्रैवर्सल प्रदर्शन करते हैं।

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
जावा प्रोग्राम
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. समय जटिलता: टी (एन) = ओ (आर * सी), हम मैट्रिक्स के प्रत्येक सेल को एक बार ठीक करते हैं।
  2. अंतरिक्ष जटिलता: A (n) = O (R * C), चूंकि हमने एक और मैट्रिक्स स्पेस का उपयोग नहीं किया है जो इस बात का ट्रैक रखता है कि किसी विशेष सेल का दौरा किया गया है या नहीं, हम बस ग्रिड मानों को संशोधित करते हैं ताकि विज़िट की गई कोशिकाएं चिह्नित हों जैसा देखा गया।

पहले चौड़ाई खोजो

द्वीप के अधिकतम क्षेत्र के लिए दृष्टिकोण

हम Iteratively कोशिकाओं के सभी पड़ोसियों (और इन पड़ोसियों) पर जाकर सबसे बड़े द्वीप के क्षेत्र की गणना करने का लक्ष्य रखते हैं जिनमें 1. शामिल हैं। पड़ोसियों और पड़ोसियों के पड़ोसियों को यह पुनरावृत्ति बीएफएस प्रदर्शन करके हासिल की जाती है। BFS का प्रदर्शन करते समय हम चलने वाले प्रत्येक नए सेल (1 के केवल युक्त) के लिए 1 द्वारा विज़िट किए गए कुल क्षेत्र को बढ़ाते हैं।

द्वीप के अधिकतम क्षेत्र के लिए एल्गोरिथ्म

  1. 2 डी युक्त प्रत्येक कोशिका से 1 डी ग्रिड का प्रदर्शन बीएफएस ट्रैवर्सल करें।
  2. सेल वैल्यू को 0 में बदलकर वर्तमान सेल को चिह्नित करें।
  3. वर्तमान सेल से शुरू होने वाले द्वीप का क्षेत्रफल 1 है।
  4. वर्तमान कोशिकाओं के सभी पड़ोसियों (ऊपर-दाएं-नीचे-बाएँ) पर जाएँ, जिनमें 1 सम्‍मिलित है, इन पड़ोसियों का दौरा किया के रूप में चिह्नित करें, और हर वैध पड़ोसी (मान 1 के साथ कोशिकाओं) के लिए क्षेत्र में 1 वृद्धि करें (सेल मान बदलकर ०)।
  5. ट्रैवर्सल के पूर्ण होने के बाद प्राप्त क्षेत्र वापस आ जाता है।
  6. 2,3,4 (युक्त मैट्रिक्स) में से प्रत्येक के लिए चरण 5 और 1 को निष्पादित करें और प्राप्त किए गए सभी क्षेत्र मानों की अधिकतम वापसी करें।

ऊपर दिए गए उदाहरण ग्रिड पर विचार करें: हम सबसे बड़े द्वीप के बाएं-सबसे और शीर्ष-सबसे सेल से शुरू करते हैं जिसका मूल्य 1 है (अब तक, इस सेल के ऊपर और बाएं सभी सेल पहले ही देखे जा चुके हैं) और बीएफएस ट्रैवर्सल प्रदर्शन करते हैं।

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
जावा प्रोग्राम
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. समय जटिलता: टी (एन) = ओ (आर * सी), हम मैट्रिक्स के प्रत्येक सेल को एक बार ठीक करते हैं।
  2. अंतरिक्ष जटिलता: A (n) = O (R * C)। चूँकि हमने एक और मैट्रिक्स स्पेस का उपयोग नहीं किया है जो इस बात का ट्रैक रखता है कि किसी विशेष सेल का दौरा किया गया है या नहीं, हम बस ग्रिड मानों को संशोधित करते हैं ताकि विज़िट की गई सेल को चिह्नित के रूप में चिह्नित किया जाए।

संदर्भ