পাইথনে একটি ম্যাট্রিক্সে বৃহত্তম দ্বীপের এলাকা খুঁজে বের করার প্রোগ্রাম

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

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

তাহলে আউটপুট হবে 6।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি ম্যাট্রিক্স, r, c
লাগবে
• মোট :=মোট + 1
• ম্যাট্রিক্স[r, c] :=0
• যদি r - 1>=0 এবং ম্যাট্রিক্স[r - 1, c] 1 এর মত হয়, তাহলে
  • dfs(matrix, r - 1, c)
• যদি c - 1>=0 এবং ম্যাট্রিক্স[r, c - 1] 1 এর মত হয়, তাহলে
  • dfs(matrix, r, c - 1)
• যদি r + 1
• dfs(matrix, r + 1, c)

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

উদাহরণ

শ্রেণির সমাধান:def solve(self, matrix):self.r_len =len(matrix) self.c_len =len(ম্যাট্রিক্স[0]) max_island =0 রেঞ্জে r এর জন্য(self.r_len):রেঞ্জে c এর জন্য (self.c_len):যদি ম্যাট্রিক্স[r][c] ==1:self.total =0 self.dfs(matrix, r, c) max_island =max(max_island, self.total) max_island def dfs(self, ম্যাট্রিক্স, আর, সি):self.total +=1 ম্যাট্রিক্স[r][c] =0 যদি r - 1>=0 এবং ম্যাট্রিক্স[r - 1][c] ==1:self.dfs(matrix, r) - 1, c) যদি c - 1>=0 এবং ম্যাট্রিক্স[r][c - 1] ==1:self.dfs(ম্যাট্রিক্স, r, c - 1) যদি r + 1  
ইনপুট
 <প্রি>ম্যাট্রিক্স =[[0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0 , 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0 ] 

আউটপুট

6