C++ में एक बड़ा द्वीप बनाना

मान लीजिए कि हमारे पास बाइनरी मानों (0s और 1s) का 2D ग्रिड है, हम अधिकतम 0 से 1 में बदलते हैं। उसके बाद हमें यह पता लगाना होगा कि सबसे बड़े द्वीप का आकार क्या है ? यहां एक द्वीप 1s का 4-प्रत्यक्ष रूप से (ऊपर, नीचे, बाएं, दाएं) जुड़ा हुआ समूह है।

इसलिए, यदि इनपुट [[1, 0], [0, 1]] जैसा है, तो आउटपुट 3 होगा, ऐसा इसलिए है क्योंकि यदि हम एक 0 से 1 को बदलते हैं और दो 1s को जोड़ते हैं, तो हमें एक द्वीप मिलेगा क्षेत्र =3.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार की एक सरणी डीआईआर परिभाषित करें:4 x 2, डीआईआर:={{1, 0}, {- 1, 0}, {0, 1}, {0, - 1}}

• एक फ़ंक्शन को परिभाषित करें dfs(), यह idx, i, j, ग्रिड लेगा,

• अगर (i,j) ग्रिड क्षेत्र के अंदर हैं और ग्रिड[i, j] 1 के बराबर नहीं है, तो -

  • वापसी 0

• रिट :=1

• ग्रिड [i, j] :=idx

• इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

  • नी:=डीआईआर [के, 0] + आई, एनजे:=डीआईआर [के, 1] + जे

  • रिट:=रिट + डीएफएस (ग्रिड, नी, एनजे, आईडीएक्स)

• वापसी रिट

• मुख्य विधि से, निम्न कार्य करें -

• रिट:=0, आईडीएक्स:=2

• आकार 2 के सरणी क्षेत्र को परिभाषित करें

• n :=ग्रिड की पंक्ति गणना, m :=ग्रिड की स्तंभ संख्या

• इनिशियलाइज़ i:=0 के लिए, जब i

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • अगर ग्रिड [i, j] 1 के समान है, तो -

      • क्षेत्र के अंत में dfs (ग्रिड, i, j, idx) डालें

      • ret :=अधिकतम रिट और क्षेत्र का अंतिम तत्व

      • (आईडीएक्स को 1 से बढ़ाएं)

• इनिशियलाइज़ i:=0 के लिए, जब i

  • अगर ग्रिड [i, j] 0 के समान है, तो -

    • एक सेट आईडीएक्स परिभाषित करें

    • इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

      • नी:=आई + डीआईआर [के, 0], एनजे:=जे + डीआईआर [के, 1]

      • यदि ni,nj ग्रिड की सीमा में है, तो -

        • अगर ग्रिड [नी, एनजे] शून्य नहीं है, तो -

          • idxs में ग्रिड [ni, nj] डालें

    • अस्थायी:=1

    • idxs में सभी तत्वों के लिए, −

      . करें

      • अस्थायी:=अस्थायी + क्षेत्र [यह]

      • (इसे 1 से बढ़ाएं)p + क्षेत्र[यह]

  • ret :=अधिकतम रिट और अस्थायी

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   int dfs(vector < vector <int> >& grid, int i, int j, int idx){
      if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()
      || grid[i][j] != 1) return 0;
      int ret = 1;
      grid[i][j] = idx;
      for(int k = 0; k < 4; k++){
         int ni = dir[k][0] + i;
         int nj = dir[k][1] + j;
         ret += dfs(grid, ni, nj, idx);
      }
      return ret;
   }
   int largestIsland(vector<vector<int>>& grid) {
      int ret = 0;
      int idx = 2;
      vector <int > area(2);
      int n = grid.size();
      int m = grid[0].size();
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 1){
               area.push_back(dfs(grid, i, j, idx));
               ret = max(ret, area.back());
               idx++;
            }
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 0){
               set <int> idxs;
               for(int k = 0; k < 4; k++){
                  int ni = i + dir[k][0];
                  int nj = j + dir[k][1];
                  if(ni < 0 || nj < 0 || ni >= grid.size() ||
                  nj >= grid[0].size()) continue;
                  if(grid[ni][nj]){
                     idxs.insert(grid[ni][nj]);
                  }
               }
               int temp = 1;
               set <int> :: iterator it = idxs.begin();
               while(it != idxs.end()){
                  temp += area[*it];
                  it++;
               }
               ret = max(ret, temp);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,0},{0,1}};
   cout << (ob.largestIsland(v));
}

इनपुट

{{1,0},{0,1}}

आउटपुट

3