पायथन में दिए गए मैट्रिक्स में 1s के सबसे बड़े वर्ग का क्षेत्रफल ज्ञात करने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, हमें उस दिए गए मैट्रिक्स में 1s का सबसे बड़ा वर्ग खोजना होगा।

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

1	0	0	0	0	1	1
0	0	0	0	0	1	1
0	1	1	1	1	0	0
0	1	1	1	1	0	0
0	1	1	1	1	0	0
0	1	1	1	1	0	0

तो आउटपुट 16 होगा।

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

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

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

उदाहरण

class Solution:
   def solve(self, matrix):
      res = 0
      for i in range(len(matrix)):
         res = max(res, matrix[i][0])
      for i in range(len(matrix[0])):
         res = max(res, matrix[0][i])

      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) + 1

               res = max(res, matrix[i][j])

      return res * res

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

इनपुट

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