C++ এ ছিটমহলের সংখ্যা

ধরুন আমরা একটি 2D অ্যারে A দিয়েছি, এখন প্রতিটি সেল হল 0 (সমুদ্রের প্রতিনিধিত্ব করে) বা 1 (ভূমির প্রতিনিধিত্ব করে) এখানে একটি পদক্ষেপ হল একটি ভূমি বর্গ 4-দিক থেকে অন্য ল্যান্ড বর্গক্ষেত্রে বা গ্রিডের সীমানার বাইরে হাঁটা। আমাদের গ্রিডের ভূমি বর্গক্ষেত্রের সংখ্যা খুঁজে বের করতে হবে যার জন্য আমরা যেকোন সংখ্যক চালে গ্রিডের সীমানা ছাড়িয়ে যেতে পারি না। তাই যদি গ্রিড −

উত্তর হবে 3, কারণ তিনটি 0s দ্বারা আবদ্ধ আছে, এবং একটি 1 আবদ্ধ নয়।

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

• একটি দিক নির্দেশনা বিন্যাস করুন, এবং [[1,0], [-1,0], [0,1], [0,-1]]

• dfs() নামে একটি পদ্ধতি তৈরি করুন এতে x, y এবং ম্যাট্রিক্স A

  লাগবে

• যদি x <0 বা y> 0 বা x> A এর সারি গণনা বা y> A এর কলামের সংখ্যা, বা A[x, y] 0 হয়, তাহলে ফিরে আসুন

• A[x, y] :=0

  সেট করুন

• k এর জন্য 0 থেকে 3

  পরিসরে

  • nx :=dir[k, 0] + x, ny :=dir[k, 1] + y

  • dfs(nx, ny, A)

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

• ret :=0, n :=A

  এর সারি গণনা

• m :=A-এর কলাম সংখ্যা যদি n 0 না হয়, অন্যথায় m :=0

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • যদি A[i, 0] =1 হয়, তাহলে dfs(i, 0, A) কে কল করুন

  • যদি A[i, m – 1] 1 হয়, তাহলে dfs(i, m – 1, A) কল করুন

• আমি 0 থেকে m – 1

  পরিসরে

  • যদি A[0, i] =1 হয়, তাহলে dfs(0, i, A)

    কে কল করুন

  • যদি A[n – 1, i] 1 হয়, তাহলে dfs(n – 1, i, A) কল করুন

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • j-এর জন্য 0 থেকে m – 1

    পরিসরে

    • ret :=ret + A[i, j]

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

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   void dfs(int x, int y, vector < vector <int>>& A){
      if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() ||
      A[x][y] == 0) return;
      A[x][y] = 0;
      for(int k = 0; k < 4; k++){
         int nx = dir[k][0] + x;
         int ny = dir[k][1] + y;
         dfs(nx, ny, A);
      }
   }
   int numEnclaves(vector<vector<int>>& A) {
      int ret = 0;
      int n = A.size();
      int m = n ? A[0].size() : 0;
      for(int i = 0; i < n; i++){
         if(A[i][0] == 1){
            dfs(i, 0, A);
         }
         if(A[i][m - 1] == 1){
            dfs(i, m - 1, A);
         }
      }
      for(int i = 0; i < m; i++){
         if(A[0][i] == 1){
            dfs(0, i, A);
         }
         if(A[n - 1][i] == 1){
            dfs(n - 1, i, A);
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            ret += A[i][j];
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
   Solution ob;
   cout << (ob.numEnclaves(v1));
}

ইনপুট

[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

আউটপুট

3