C++ এ একটি বড় দ্বীপ তৈরি করা

ধরুন আমাদের কাছে বাইনারি মানের একটি 2D গ্রিড আছে (0s এবং 1s), আমরা সর্বাধিক এক 0 থেকে 1 এ পরিবর্তন করি। এর পরে আমাদের খুঁজে বের করতে হবে বৃহত্তম দ্বীপের আকার কত? ? এখানে একটি দ্বীপ হল একটি 4-দিকনির্দেশক (উপর, নীচে, বাম, ডান) 1s এর সংযুক্ত গ্রুপ৷

সুতরাং, যদি ইনপুটটি [[1, 0], [0, 1]] এর মতো হয় তবে আউটপুট হবে 3, এর কারণ যদি আমরা একটি 0 থেকে 1 পরিবর্তন করি এবং দুটি 1s সংযোগ করি, তাহলে আমরা একটি দ্বীপ পাব এলাকা =3.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আকারের একটি অ্যারে ডিআইর সংজ্ঞায়িত করুন:4 x 2, dir :={{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি idx, i, j, গ্রিড,

• যদি (i,j) গ্রিড অঞ্চলের ভিতরে থাকে এবং গ্রিড[i, j] 1 এর সমান না হয়, তাহলে −

  • রিটার্ন 0

• ret :=1

• গ্রিড[i, j] :=idx

• আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

  • ni :=dir[k, 0] + i, nj :=dir[k, 1] + j

  • ret :=ret + dfs(গ্রিড, ni, nj, idx)

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• ret :=0, idx :=2

• আকার 2

  এর একটি অ্যারে এলাকা সংজ্ঞায়িত করুন

• n :=গ্রিডের সারি গণনা, m :=গ্রিডের কলাম গণনা

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=0, যখন j করুন

    • যদি গ্রিড[i, j] 1 এর মত হয়, তাহলে −

      • এলাকার শেষে dfs(grid, i, j, idx) সন্নিবেশ করুন

      • ret :=ret এর সর্বোচ্চ এবং ক্ষেত্রফলের শেষ উপাদান

      • (আইডিএক্স 1 দ্বারা বাড়ান)

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি গ্রিড[i, j] 0 এর মত হয়, তাহলে −

    • একটি সেট idxs সংজ্ঞায়িত করুন

    • আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

      • ni :=i + dir[k, 0],nj :=j + dir[k, 1]

      • যদি ni,nj গ্রিডের পরিসরে থাকে, তাহলে −

        • যদি গ্রিড[ni, nj] অ-শূন্য হয়, তাহলে −

          • idxs এ গ্রিড[ni, nj] সন্নিবেশ করান

    • তাপমাত্রা :=1

    • idxs-এ সমস্ত উপাদানের জন্য, −

      করুন

      • temp :=temp + এলাকা[এটি]

      • (এটি 1 দ্বারা বৃদ্ধি করুন)p + এলাকা[এটি]

  • ret :=সর্বোচ্চ ret এবং temp

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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