अजगर में 1 के साथ वर्ग सबमैट्रिस की संख्या खोजने का कार्यक्रम

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

तो, अगर इनपुट पसंद है

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

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

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

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

उदाहरण

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