Chương trình tìm diện tích hình vuông lớn nhất của 1s trong một ma trận cho trước trong python

Giả sử chúng ta có một ma trận nhị phân, chúng ta phải tìm bình phương 1s lớn nhất trong ma trận đã cho đó.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 16.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=0
• đối với tôi trong phạm vi từ 0 đến kích thước của ma trận, hãy thực hiện
  • res:=tối đa của res và ma trận [i, 0]
• đối với tôi trong phạm vi từ 0 đến kích thước của ma trận [0], hãy thực hiện
  • res:=tối đa của res và ma trận [0, i]
• đối với tôi trong phạm vi 1 đến số hàng của ma trận, hãy thực hiện
  • đối với j trong phạm vi 1 đến số cột của ma trận, thực hiện
    • nếu ma trận [i, j] giống 1, thì
      • ma trận [i, j] =tối thiểu của (ma trận [i - 1, j], ma trận [i - 1, j - 1] và ma trận [i, j - 1]) + 1
    • res =tối đa của res và ma trận [i, j]
• trả về res ^ 2

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

16