파이썬에서 주어진 행렬에서 1의 가장 큰 제곱의 면적을 찾는 프로그램

이진 행렬이 있다고 가정하고 주어진 행렬에서 1의 가장 큰 제곱을 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 16이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• res :=0
• 행렬 크기 범위 0에서 i에 대해
  • res :=res 및 matrix[i, 0]의 최대값
• 행렬 [0]의 크기 범위 0에 있는 i에 대해
  • res :=res 및 matrix[0, i]의 최대값
• 행렬의 행 수까지 범위 1에 있는 i에 대해 다음을 수행합니다.
  • 행렬의 열 개수에 대한 범위 1의 j에 대해 다음을 수행합니다.
    • 행렬[i,j]가 1과 같으면
      • 행렬[i, j] =(행렬[i - 1, j], 행렬[i - 1, j - 1] 및 행렬[i, j - 1]) + 1의 최소값
    • res =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] ]

출력

16