Python을 사용하여 모든 1로 정사각형 부분행렬의 수를 계산하는 프로그램

m x n 이진 행렬이 있다고 가정하고 모두 1을 갖는 정사각형 부분행렬의 수를 찾아야 합니다.

그래서, 입력이 같다면.

그러면 1변에 10개의 정사각형이 있으므로 출력은 15가 됩니다. 변 2에 4개의 정사각형과 변 3에 1개의 정사각형이 있습니다. 그러면 총 정사각형 수 =10 + 4 + 1 =15입니다.

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

• 행렬에 하나의 행렬이 있으면

  • 1 반환

• 행 :=행렬의 행 수

• cols :=행렬[0]의 열 개수

• 결과 :=0

• 범위 0에서 행 - 1의 행에 대해 수행

  • 0에서 cols - 1 범위의 col에 대해 수행

    • 행이 0과 같거나 열이 0과 같으면

      • 행렬[row, col]이 1과 같으면

        • 결과 :=결과 + 1

      • 그렇지 않으면 행렬[row, col]이 1과 같을 때

        • 정사각형 :=1 + (행렬[row-1,col], 행렬[row,col-1] 및 행렬[row-1,col-1]의 최소값)

        • 행렬[행, 열] :=정사각형

        • 결과 :=결과 + 제곱

• 반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

def solve(matrix):
   if matrix == [[1]]:
      return 1
   rows = len(matrix)
   cols = len(matrix[0])
   result = 0
   for row in range(rows):
      for col in range(cols):
         if (row == 0 or col == 0):
            if matrix[row][col] == 1:
               result += 1
         elif matrix[row][col] == 1:
            square = min(matrix[row-1][col], min(matrix[row][col-1], matrix[row-1][col-1])) + 1
            matrix[row][col] = square
            result += square
   return result
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
print(solve(matrix))

입력

{{0,1,1,1},{1,1,1,1},{0,1,1,1}}

출력

15