পাইথনে 1 সহ বর্গাকার সাবমেট্রিসের সংখ্যা খুঁজে বের করার প্রোগ্রাম

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

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

তাহলে আউটপুট 17 হবে কারণ 12 (1 x 1) বর্গ, 4 (2 x 2) বর্গ এবং 1 (3 x 3) বর্গ রয়েছে।

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

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

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

উদাহরণ

শ্রেণির সমাধান:def solve(self, matrix):res =0 for i in range(len(matrix)):j এর জন্য রেঞ্জ(len(matrix[0])):যদি i ==0 বা j ==0:res +=ম্যাট্রিক্স[i][j] elif ম্যাট্রিক্স[i][j] ==1:ম্যাট্রিক্স[i][j] =min(matrix[i][j - 1], matrix[i - 1 ][j], ম্যাট্রিক্স[i - 1][j - 1]) + 1 রেস +=ম্যাট্রিক্স[i][j] রিটার্ন resob =সমাধান()ম্যাট্রিক্স =[ [ [1, 1, 1, 0], [1 , 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0], [1, 0, 1, 1]]মুদ্রণ(ob.solve(matrix))

ইনপুট

আউটপুট

17