पायथन में दिए गए बाइनरी मैट्रिक्स में वर्ग सबमैट्रिस की संख्या गिनने का कार्यक्रम

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

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

तो आउटपुट 5 होगा, क्योंकि एक (2 × 2) वर्ग है, और चार (1 × 1) वर्ग हैं

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

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

उदाहरण

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

def solve(mat):
   if mat == []:
      return 0
   c = 0

   for i in range(len(mat)):
      for j in range(len(mat[0])):
         if mat[i][j] == 1:
            if i == 0 or j == 0:
               c += 1
            else:
               temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
               c += temp
               mat[i][j] = temp
   return c

matrix = [
   [0, 1, 1],
   [0, 1, 1]
]
print(solve(matrix))

इनपुट

[[2, 6],[3, 4],[4, 7],[5, 5]]

आउटपुट

5