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

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

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

1	0	1
0	1	1
0	1	1

কারণ এখানে ৬টি ১×১, ৩টি ২×১, ২টি ১×২, ১টি ৩×১ এবং ১টি ২×২ সাবম্যাট্রিক্স রয়েছে যেগুলোর সব উপাদান ১।

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

m := ম্যাট্রিক্সের সারি সংখ্যা
n := ম্যাট্রিক্সের কলাম সংখ্যা
dp := একই আকারের শূন্য ম্যাট্রিক্স
i = 0 থেকে m-1 পর্যন্ত লুপ:

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

যদি i == 0 এবং matrix[i][j] == 1 হয়, তবে dp[i][j] := 1
অন্যথায় যদি matrix[i][j] != 0 হয়, তবে dp[i][j] := dp[i-1][j] + 1

total := 0
i = 0 থেকে m-1 পর্যন্ত লুপ:

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

k = j+1 থেকে n পর্যন্ত লুপ:

total := total + min(dp[i][j] থেকে dp[i][k-1] পর্যন্ত)

total ফেরত দিন।

উদাহরণ

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

ইনপুট

[[1,0,1],[0,1,1],[0,1,1]]