在python中找到给定矩阵中最大的1的正方形的面积

假设我们有一个二进制矩阵，我们必须在该给定矩阵中找到最大的1正方形。

如果输入如下所示

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

那么输出将是16。

为了解决这个问题，我们将遵循以下步骤−

res := 0
for i in range 0 to size of matrix, do
- res := maximum of res and matrix[i, 0]
for i in range 0 to size of matrix[0], do
- res := maximum of res and matrix[0, i]
for i in range 1 to row count of matrix, do
- for j in range 1 to column count of matrix, do
  - if matrix[i, j] is same as 1, then
  - matrix[i, j] = minimum of (matrix[i – 1, j], matrix[i – 1, j – 1] and matrix[i, j – 1]) + 1
  - res = maximum of res and matrix[i, j]
return res^2

让我们看看以下实现以获得更好的理解 −

更多Python相关文章，请阅读：Python 教程

示例

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