Python에서 주어진 이진 행렬의 정사각형 부분 행렬 수를 계산하는 프로그램

<시간/>

2D 이진 행렬이 있다고 가정합니다. 모든 요소가 1인 행렬에 있는 정사각형 부분행렬의 총 수를 찾아야 합니다.

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

0	1	1
0	1	1

1(2 × 2) 정사각형과 4(1 × 1) 정사각형이 있기 때문에 출력은 5가 됩니다.

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

매트가 비어 있으면
- 0을 반환
c :=0
0 범위에서 매트의 행 수까지 i에 대해
- 0 범위에서 매트의 열 수까지의 j에 대해 다음을 수행합니다.
  - mat[i,j]가 1이면
    - i가 0이거나 j가 0이면
      - c :=c + 1
    - 그렇지 않으면
      - temp =((mat[i-1, j-1], mat[i, j-1] 및 mat[i-1, j]) + mat[i, j]의 최소값
      - c :=c + 온도
      - 매트[i, j] :=온도
반환 c

예시

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

def solve(mat):
   if mat == []:
      return 0
   c = 0

   for i in range(len(mat)):
      for j in range(len(mat[0])):
         if mat[i][j] == 1:
            if i == 0 or j == 0:
               c += 1
            else:
               temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
               c += temp
               mat[i][j] = temp
   return c

matrix = [
   [0, 1, 1],
   [0, 1, 1]
]
print(solve(matrix))

입력

[[2, 6],[3, 4],[4, 7],[5, 5]]