बाइनरी मैट्रिक्स में 1 वाले वर्ग सबमैट्रिक्स की संख्या ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है, हमें उन वर्ग सबमैट्रिक्स की कुल संख्या ढूंढनी है जिनमें सभी 1 हैं।

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

तो आउटपुट 17 होगा क्योंकि 12 (1 x 1) वर्ग, 4 (2 x 2) वर्ग और 1 (3 x 3) वर्ग हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• res := 0
• i को 0 से मैट्रिक्स की पंक्ति संख्या तक के लिए, करें
  • j को 0 से मैट्रिक्स की स्तंभ संख्या तक के लिए, करें
    • यदि i, 0 के समान है या j, 0 के समान है, तो
      • res := res + matrix[i, j]
    • अन्यथा जब matrix[i, j] 1 के समान है, तो
      • matrix[i, j] = (matrix[i, j - 1], matrix[i - 1, j] और matrix[i - 1, j - 1]) का न्यूनतम + 1
      • res := res + matrix[i, j]
• res लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, matrix):
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i == 0 or j == 0:
                    res += matrix[i][j]
                elif matrix[i][j] == 1:
                    matrix[i][j] = min(matrix[i][j - 1], matrix[i - 1][j], matrix[i - 1][j - 1]) + 1
                    res += matrix[i][j]
        return res

ob = Solution()
matrix = [
    [1, 1, 1, 0],
    [1, 1, 1, 0],
    [1, 1, 1, 0],
    [0, 0, 0, 0],
    [1, 0, 1, 1]
]
print(ob.solve(matrix))

इनपुट

matrix = [
    [1, 1, 1, 0],
    [1, 1, 1, 0],
    [1, 1, 1, 0],
    [0, 0, 0, 0],
    [1, 0, 1, 1]
]

आउटपुट

17