পাইথন ব্যবহার করে সকলের সাথে সাবমেট্রিস গণনা করার প্রোগ্রাম

ধরুন আমাদের m x n বাইনারি ম্যাট্রিক্স আছে, আমাদের খুঁজে বের করতে হবে কয়টি সাবমেট্রিকে সবগুলো আছে।

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

তাহলে আউটপুট 13 হবে কারণ এখানে 6 (1x1) ম্যাট্রিক্স, 3 (2,1) ম্যাট্রিক্স, 2 (1x2) ম্যাট্রিক্স, 1 (3x1) ম্যাট্রিক্স এবং 1 (4x4) ম্যাট্রিক্স রয়েছে।

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

• m :=ম্যাট্রিক্সের সারি গণনা

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

• dp :=একই আকারের একটি শূন্য ম্যাট্রিক্স m x n

• আমি 0 থেকে m - 1 রেঞ্জের জন্য, কর

  • 0 থেকে n - 1 রেঞ্জে j এর জন্য, করুন

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

      • dp[i, j] :=1

    • অন্যথায় যখন ম্যাট্রিক্স[i][j] অ-শূন্য হয়, তখন

      • dp[i, j] :=dp[i-1, j] + 1

• মোট :=0

• আমি 0 থেকে m - 1 রেঞ্জের জন্য, কর

  • 0 থেকে n - 1 রেঞ্জে j এর জন্য, করুন

    • j+1 থেকে n রেঞ্জে k-এর জন্য, করুন

      • মোট :=মোট + সর্বনিম্ন dp[i,j] থেকে dp[i,k]

• মোট রিটার্ন

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

উদাহরণ

def solve(matrix):
   m = len(matrix)
   n = len(matrix[0])
   dp = [[0] * n for _ in range(m)]
   for i in range(m):
      for j in range(n):
         if i == 0 and matrix[i][j]:
            dp[i][j] = 1
         elif matrix[i][j]:
            dp[i][j] = dp[i-1][j] + 1
   total = 0
   for i in range(m):
      for j in range(n):
         for k in range(j+1, n+1):
            total += min(dp[i][j:k])
   return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

ইনপুট

[4,6,7,8], 11

আউটপুট

13