पायथन का उपयोग करके सभी 1 वाले सबमैट्रिक्स की गिनती करने का प्रोग्राम

मान लीजिए हमारे पास m x n बाइनरी मैट्रिक्स है, हमें ढूंढना है कि कितने सबमैट्रिक्स में सभी 1 हैं।

उदाहरण के लिए, यदि इनपुट इस तरह है:

तो आउटपुट 13 होगा क्योंकि 6 (1x1) मैट्रिक्स, 3 (2x1) मैट्रिक्स, 2 (1x2) मैट्रिक्स, 1 (3x1) मैट्रिक्स और 1 (2x2) मैट्रिक्स हैं।

हल करने के चरण

• m := मैट्रिक्स की पंक्ति संख्या

• n := मैट्रिक्स की स्तंभ संख्या

• dp := समान आकार m x n का एक शून्य मैट्रिक्स

• i को 0 से m - 1 तक की रेंज में लिए करें

  • j को 0 से n - 1 तक की रेंज में लिए करें

    • यदि i, 0 के समान है और matrix[i][j], तो

      • dp[i][j] := 1

    • अन्यथा जब matrix[i][j] शून्येतर है, तो

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

• total := 0

• i को 0 से m - 1 तक की रेंज में लिए करें

  • j को 0 से n - 1 तक की रेंज में लिए करें

    • k को j+1 से n तक की रेंज में लिए करें

      • total := total + dp[i][j] से dp[i][k] का न्यूनतम

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

आउटपुट

13