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

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

उदाहरण के लिए, यदि इनपुट इस तरह है:

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 := res और matrix[i, 0] में से अधिकतम
i को 0 से matrix[0] के आकार तक के लिए, करें
- res := res और matrix[0, i] में से अधिकतम
i को 1 से मैट्रिक्स की पंक्ति संख्या तक के लिए, करें
- j को 1 से मैट्रिक्स की स्तंभ संख्या तक के लिए, करें
  - यदि matrix[i, j] 1 के समान है, तो
    - matrix[i, j] = (matrix[i - 1, j], matrix[i - 1, j - 1] और matrix[i, j - 1]) का न्यूनतम + 1
  - res = res और matrix[i, j] में से अधिकतम
res^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]
]