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

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

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

तो आउटपुट 15 होगा, क्योंकि भुजा 1 के 10 वर्ग हैं। भुजा 2 के 4 वर्ग और भुजा 3 का 1 वर्ग। तब वर्गों की कुल संख्या =10 + 4 + 1 =15.

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

• अगर मैट्रिक्स में सिंगल है, तो

  • वापसी 1

• पंक्तियाँ :=मैट्रिक्स की पंक्ति गणना

• cols :=मैट्रिक्स की कॉलम संख्या[0]

• परिणाम:=0

• 0 से पंक्तियों -1 तक की पंक्ति के लिए करें

  • 0 से लेकर cols - 1 तक के कर्नल के लिए करें

    • यदि पंक्ति 0 के समान है या col 0 के समान है, तो

      • यदि मैट्रिक्स [पंक्ति, col] 1 के समान है, तो

        • परिणाम:=परिणाम + 1

      • अन्यथा जब मैट्रिक्स [पंक्ति, कॉल] 1 के समान हो, तो

        • वर्ग:=1 + (न्यूनतम मैट्रिक्स [पंक्ति -1, कर्नल], मैट्रिक्स [पंक्ति, कॉलम -1] और मैट्रिक्स [पंक्ति -1, कॉलम -1])

        • मैट्रिक्स [पंक्ति, col] :=वर्ग

        • परिणाम:=परिणाम + वर्ग

• वापसी परिणाम

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

उदाहरण

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

आउटपुट

15