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

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

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

তাহলে আউটপুট হবে 15, কারণ পাশের 10টি বর্গক্ষেত্র রয়েছে। পাশে 2 এর 4টি বর্গ এবং 3টি পাশের 1টি বর্গ। তারপর মোট বর্গ সংখ্যা =10 + 4 + 1 =15।

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

• যদি ম্যাট্রিক্সে একক থাকে, তাহলে

  • রিটার্ন 1

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

• cols :=ম্যাট্রিক্সের কলাম সংখ্যা[0]

• ফলাফল :=0

• 0 থেকে সারি - 1 পর্যন্ত সারির জন্য, করুন

  • 0 থেকে col - 1 রেঞ্জের col-এর জন্য, do

    • যদি সারি 0 এর মত হয় বা কল 0 এর মত হয়, তাহলে

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

        • ফলাফল :=ফলাফল + 1

      • অন্যথায় যখন ম্যাট্রিক্স[সারি, কল] 1 এর মত হয়, তখন

        • বর্গ :=1 + (সর্বনিম্ন ম্যাট্রিক্স[সারি-1,কল], ম্যাট্রিক্স[রো,কল-1] এবং ম্যাট্রিক্স[রো-1,কল-1])

        • ম্যাট্রিক্স[সারি, কল] :=বর্গ

        • ফলাফল :=ফলাফল + বর্গ

• ফেরত ফলাফল

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

উদাহরণ

def solve(matrix):
   if matrix == [[1]]:
      return 1
   rows = len(matrix)
   cols = len(matrix[0])
   result = 0
   for row in range(rows):
      for col in range(cols):
         if (row == 0 or col == 0):
            if matrix[row][col] == 1:
               result += 1
         elif matrix[row][col] == 1:
            square = min(matrix[row-1][col], min(matrix[row][col-1], matrix[row-1][col-1])) + 1
            matrix[row][col] = square
            result += square
   return result
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
print(solve(matrix))

ইনপুট

{{0,1,1,1},{1,1,1,1},{0,1,1,1}}

আউটপুট

15