C++ এ বন্ধ দ্বীপের সংখ্যা

ধরুন আমাদের একটি 2D গ্রিড 0s (ভূমি হিসাবে) এবং 1s (জল হিসাবে) নিয়ে গঠিত। একটি দ্বীপ হল 0 সেকেন্ডের সর্বাধিক 4- দিকনির্দেশকভাবে সংযুক্ত গ্রুপ। একটি বদ্ধ দ্বীপ হল একটি দ্বীপ যা সম্পূর্ণভাবে 1s দ্বারা বেষ্টিত। আমাদের বদ্ধ দ্বীপের সংখ্যা খুঁজে বের করতে হবে। তাই যদি গ্রিডের মত হয়

সুতরাং আউটপুট হবে 2। এখানে দুটি দ্বীপ রয়েছে, যেগুলো সম্পূর্ণরূপে পানি দ্বারা বেষ্টিত।

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

• একটি পরিবর্তনশীল পতাকা সংজ্ঞায়িত করুন

• dfs নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি গ্রিড, i, j, n এবং m

  নেবে।
• যদি i এবং j গ্রিডের রেঞ্জের মধ্যে না থাকে, তাহলে পতাকা সেট করুন :=false এবং return

• যদি g[i,j] =1 বা g[i, j] =-1 হয়, তাহলে ফেরত দিন

• যদি g[i, j] =0 হয়, তাহলে g[i, j] =-1

• কল করুন dfs(g, i + 1, j, n, m), dfs(g, i, j+1, n, m), dfs(g, i - 1, j, n, m), dfs(g, i, j-1, n, m)

• মূল পদ্ধতিটি হবে −

  এর মত

• n x m অর্ডারের একটি dp ম্যাট্রিক্স তৈরি করুন এবং -1

  দিয়ে এটি পূরণ করুন

• 0 থেকে n – 1

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

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

    পরিসরে

    • যদি g[i, j] =0, তাহলে

      • পতাকা :=সত্য

      • dfs(g, i, j, n, m)

      • পতাকা :=সত্য

      • ans :=ans + পতাকা

• উত্তর ফেরত দিন

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

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;class Solution { public:vector > dp; bool পতাকা; void dfs(ভেক্টর<ভেক্টর>&g, int i, int j, int n, int m){ if(i>=n || j>=m || i<0 || j<0){ পতাকা =মিথ্যা; প্রত্যাবর্তন; } if(g[i][j] ==1 || g[i][j] ==-1)রিটার্ন; if(g[i][j] ==0)g[i][j] =-1; dfs(g, i+1, j, n, m); dfs(g, i, j+1, n, m); dfs(g, i-1, j, n, m); dfs(g,i, j-1, n, m); } int closeIsland(ভেক্টর<ভেক্টর>&g) { int ans =0; int n =g.size(); int m =g[0].size(); dp =ভেক্টর <ভেক্টর > (n, ভেক্টর  (m, -1)); for(int i =0; i > v ={{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1, 0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0 ,1},{1,1,1,1,1, 1,1,0}}; সমাধান ob; cout <<(ob.closedIsland(v));}

ইনপুট

আউটপুট

2