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

ধরুন আমাদের একটি 2D বাইনারি ম্যাট্রিক্স আছে। আমাদের ম্যাট্রিক্সে উপস্থিত বর্গ সাবমেট্রিসের মোট সংখ্যা খুঁজে বের করতে হবে, যেখানে সমস্ত উপাদান 1।

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

তাহলে আউটপুট হবে 5, কারণ এখানে একটি (2 × 2) বর্গ এবং চারটি (1 × 1) বর্গ রয়েছে

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

• যদি মাদুর খালি থাকে, তাহলে
  • রিটার্ন 0
• c :=0
• আমি পরিসীমা 0 থেকে সারির ম্যাটের সংখ্যার জন্য, করুন
  j-এর জন্য 0 থেকে স্তম্ভ গণনার পরিসরে,
  করুন
  • যদি mat[i, j] 1 হয়, তাহলে
    • যদি i 0 হয় বা j হয় 0, তাহলে
      • c :=c + 1
    • অন্যথায়,
      • temp =(ন্যূনতম (ম্যাট[i-1, j-1], mat[i, j-1] এবং mat[i-1, j]) + mat[i, j]
      • c :=c + temp
      • mat[i, j] :=temp
• রিটার্ন c

উদাহরণ

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

def solve(mat):
   if mat == []:
      return 0
   c = 0

   for i in range(len(mat)):
      for j in range(len(mat[0])):
         if mat[i][j] == 1:
            if i == 0 or j == 0:
               c += 1
            else:
               temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
               c += temp
               mat[i][j] = temp
   return c

matrix = [
   [0, 1, 1],
   [0, 1, 1]
]
print(solve(matrix))

ইনপুট

[[2, 6],[3, 4],[4, 7],[5, 5]]

আউটপুট

5