পাইথনে ম্যাট্রিক্সে বেষ্টিত দ্বীপের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। যেখানে 1 ভূমি প্রতিনিধিত্ব করে এবং 0 জলের প্রতিনিধিত্ব করে। যেমনটি আমরা জানি একটি দ্বীপ হল 1s-এর একটি দল যা একত্রে বিভক্ত যার পরিধিটি জল দ্বারা বেষ্টিত। আমাদের সম্পূর্ণ বেষ্টিত দ্বীপের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 2, কারণ তিনটি দ্বীপ আছে, কিন্তু তাদের মধ্যে দুটি সম্পূর্ণরূপে বেষ্টিত।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এর জন্য i, j
লাগবে
• যদি i এবং j ম্যাট্রিক্সের পরিসরে না হয়, তাহলে
  • মিথ্যে ফেরত দিন
• যদি ম্যাট্রিক্স[i, j] 0 এর মত হয়, তাহলে
  • সত্য ফেরান
• ম্যাট্রিক্স[i, j] :=0
• a :=dfs(i + 1, j)
• b :=dfs(i - 1, j)
• c :=dfs(i, j + 1)
• d :=dfs(i, j - 1)
• a এবং b এবং c এবং d ফেরত দিন
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
• R :=ম্যাট্রিক্সের সারি গণনা, C :=ম্যাট্রিক্সের কলাম সংখ্যা
• উত্তর :=0
• আমি 0 থেকে R রেঞ্জের জন্য, কর
  0 থেকে C রেঞ্জে j-এর জন্য
  • করুন
    • যদি ম্যাট্রিক্স[i, j] 1 এর মত হয়, তাহলে
      • যদি dfs(i, j) সত্য হয়, তাহলে
        • উত্তর :=উত্তর + ১
• উত্তর ফেরত দিন

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

উদাহরণ

শ্রেণির সমাধান:def solve(self, matrix):def dfs(i, j):যদি i <0 বা j <0 বা i>=R বা j>=C:রিটার্ন False if matrix[i][j] ] ==0:রিটার্ন ট্রু ম্যাট্রিক্স[i][j] =0 a =dfs(i + 1, j) b =dfs(i - 1, j) c =dfs(i, j + 1) d =dfs( i, j - 1) a এবং b এবং c এবং d R, C =len(matrix), len(matrix[0]) ans =0 এর জন্য i রেঞ্জে (R):রেঞ্জে j এর জন্য(C):যদি ম্যাট্রিক্স[i][j] ==1:যদি dfs(i, j):ans +=1 return ansob =Solution()matrix =[ [ [1, 0, 0, 0, 0], [0, 0, 0 , 1, 0], [0, 1, 0, 0, 0], [0, 1, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0] , 0]]print(ob.solve(matrix))

ইনপুট

আউটপুট

2