मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, हमें उस दिए गए मैट्रिक्स में 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]
- यदि मैट्रिक्स [i, j] 1 के समान है, तो
- जे के लिए श्रेणी 1 में मैट्रिक्स की कॉलम गणना के लिए, करें
- रिटर्न रेस^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] ]
आउटपुट
16