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

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে যেখানে 1 ভূমির প্রতিনিধিত্ব করে এবং 0 জলকে প্রতিনিধিত্ব করে। এবং একটি দ্বীপ হল 1s এর একটি দল যা জল দ্বারা বেষ্টিত। আমাদের সবচেয়ে বড় দ্বীপের আয়তন বের করতে হবে। আমরা সর্বাধিক একটি জল কোষকে স্থল কোষে পরিবর্তন করতে পারি৷

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

তাহলে আউটপুট হবে 7, কারণ আমরা দুটি দ্বীপকে সংযুক্ত করার জন্য একটি জল কোষকে ল্যান্ড করতে পারি। সুতরাং চূড়ান্ত ম্যাট্রিক্স হল −

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

• R :=ম্যাটের সারি গণনা, C :=ম্যাটের কলাম গণনা

• mass :=একটি নতুন মানচিত্র

• আইডি :=555

• একটি ফাংশন ফ্লাডফিল() সংজ্ঞায়িত করুন। এটি r, c, id

  লাগবে

• যদি r এবং c ম্যাট্রিক্সের পরিসরে এবং ম্যাট[r, c] 1 হয়, তাহলে

  • mat[r, c] :=id

  • mass[id] :=mass[id] + 1

  • প্রতিটি জোড়ার জন্য (r2, c2) [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ], do

    • ফ্লাডফিল(r2, c2, id)

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

• 0 থেকে R রেঞ্জের জন্য, করুন

  • 0 থেকে C রেঞ্জে c এর জন্য, করুন

    • যদি mat[r, c] 1 এর মত হয়, তাহলে

      • id :=id + 1

      • ভর [আইডি] :=0

      • ফ্লাডফিল(r, c, id)

• উত্তর :=সর্বাধিক (সমস্ত ভরের মান এবং 1)

• 0 থেকে R − 1 রেঞ্জের r-এর জন্য, করুন

  • 0 থেকে C − 1 পরিসরে c এর জন্য, করুন

    • যদি mat[r, c] 0 এর মত না হয়, তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • island_set :=একটি নতুন সেট

    • প্রতিটি জোড়ার জন্য (r2, c2) [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ], do

      • যদি r2 এবং c2 ম্যাটের পরিসরে থাকে এবং ম্যাট[r2, c2] 1 হয়, তাহলে

        • দ্বীপ_সেট

          -এ ম্যাট[r2, c2] যোগ করুন

      • উত্তর :=সর্বাধিক উত্তর এবং (1 + সমস্ত ভরের যোগফল [দ্বীপ] প্রতিটি দ্বীপ inisland_set)

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

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

উদাহরণ

শ্রেণীর সমাধান:def solve(self, mat):R, C =len(mat), len(mat[0]) mass ={} id =555 def ফ্লাডফিল(r, c, id):nonlocal R, C, mat, ভর যদি 0 <=r  
ইনপুট
 <প্রে>[[1, 0, 1],[0, 0, 0],[1, 1, 0],[1, 1, 1] ]

আউটপুট

7