পাইথনে বাইনারি ম্যাট্রিক্সে সব ১ সম্বিষ্ট বর্গাকার সাবম্যাট্রিক্স গণনা

একটি m × n বাইনারি ম্যাট্রিক্স দেওয়া আছে। আমাদের কাজ হলো কতগুলো বর্গাকার সাবম্যাট্রিক্স আছে যেগুলোর সব উপাদান ১।

যেমন, নিচের ম্যাট্রিক্সের জন্য আউটপুট ১৫:

0	1	1	1
1	1	1	1
0	1	1	1

কারণ: পাশের দৈর্ঘ্য ১ वाले ১০টি বর্গ, পাশের দৈর্ঘ্য ২ वाले ৪টি বর্গ, এবং পাশের দৈর্ঘ্য ৩ वाले ১টি বর্গ। মোট = ১০ + ৪ + ১ = ১৫।

সমাধানের ধাপসমূহ

যদি ম্যাট্রিক্স == [[1]] হয়, তবে ১ ফেরত দিন।
rows := ম্যাট্রিক্সের সারি সংখ্যা
cols := ম্যাট্রিক্সের কলাম সংখ্যা
result := 0
row = 0 থেকে rows-1 পর্যন্ত লুপ:

col = 0 থেকে cols-1 পর্যন্ত লুপ:

যদি row == 0 বা col == 0 হয়:

যদি matrix[row][col] == 1 হয়, তবে result := result + 1

অন্যথায় যদি matrix[row][col] == 1 হয়:

square := 1 + min(matrix[row-1][col], matrix[row][col-1], matrix[row-1][col-1])
matrix[row][col] := square
result := result + square

result ফেরত দিন।

উদাহরণ

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]]