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

ধরুন আমাদের একটি 2d ​​বাইনারি ম্যাট্রিক্স আছে, আমাদের প্রদত্ত ম্যাট্রিক্সে স্বতন্ত্র দ্বীপের সংখ্যা বের করতে হবে। এখানে 1 ভূমি এবং 0 জল প্রতিনিধিত্ব করে, তাই একটি দ্বীপ হল 1s এর একটি সেট যা কাছাকাছি এবং যার পরিধি জল দ্বারা বেষ্টিত। এখানে দুটি দ্বীপ অনন্য যদি তাদের আকার ভিন্ন হয়।

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

তাহলে আউটপুট হবে 4 (স্বতন্ত্র দ্বীপ ভিন্ন রঙের)।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এর জন্য i, j, k, l

  লাগবে

• mat[i, j] :=0

• আকৃতির শেষে জোড়া (i − k, j − l) সন্নিবেশ করুন

• যদি i + 1 <ম্যাট এবং ম্যাটের সারি গণনা [i + 1, j] 1 হয়, তাহলে

  • dfs(i + 1, j, k, l)

• যদি j + 1 <ম্যাট এবং ম্যাটের কলামের সংখ্যা [i, j + 1] 1 হয়, তাহলে

  • dfs(i, j + 1, k, l)

• যদি i − 1>=0 এবং mat[i − 1, j] 1 হয়, তাহলে

  • dfs(i − 1, j, k, l)

• যদি j − 1>=0 এবং mat[i, j − 1] হয় 1, তাহলে

  • dfs(i, j − 1, k, l)

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

• cnt :=0

• আকার :=একটি নতুন সেট

• আমি 0 থেকে সারির মাদুর গণনার পরিসরের জন্য, কর

  • j রেঞ্জ 0 থেকে কলামের মাদুর গণনার জন্য, করুন

    • যদি mat[i, j] 1 হয়, তাহলে

      • আকার :=একটি নতুন তালিকা

      • dfs(i, j, i, j)

      • যদি আকৃতি আকারে না হয়, তাহলে

        • cnt :=cnt + 1

      • আকারে আকৃতি সন্নিবেশ করান

• ফেরত cnt

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

উদাহরণ

শ্রেণীর সমাধান:def solve(self, mat):def dfs(i, j, k, l):mat[i][j] =0 shape.append((i − k, j − l)) যদি i + 1 =0 এবং mat[i − 1][j]:dfs(i − 1, j, k, l) যদি j −1>=0 এবং mat[i][j − 1]:dfs(i, j − 1, k, l) cnt =0 আকার =সেট() রেঞ্জে i এর জন্য(len(mat)):j এর জন্য রেঞ্জে( len(mat[0]):if mat[i][j]:shape =[] dfs(i, j, i, j) আকৃতি =tuple(আকৃতি) যদি আকৃতিতে না হয়:cnt +=1 আকার। যোগ(আকৃতি) রিটার্ন cntob =সমাধান()ম্যাট্রিক্স =[ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [ 0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1]]মুদ্রণ(ob.solve(ম্যাট্রিক্স))

ইনপুট

আউটপুট

4