파이썬에서 행렬을 k 조각으로 자르는 방법의 수를 세는 프로그램

이진 행렬과 다른 값 k가 있다고 가정합니다. 각 조각에 적어도 하나의 1이 포함되도록 행렬을 k 조각으로 분할하려고 합니다. 그러나 자르기에는 몇 가지 규칙이 있으므로 순서대로 따라야 합니다. 1. 방향 선택:수직 또는 수평 2. 행렬에서 인덱스를 선택하여 두 섹션으로 자르십시오. 3. 세로로 자르면 더 이상 왼쪽 부분을 자를 수 없고 오른쪽 부분만 계속 자를 수 있습니다. 4. 수평으로 자르면 더 이상 상단 부분을자를 수없고 하단 부분만 계속자를 수 있습니다. 따라서 행렬을 나누는 다양한 방법을 찾아야 합니다. 답변이 매우 크면 결과 모드(10^9 + 7)를 반환합니다.

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

k =2이면 출력은 4가 됩니다. 세로로 두 번, 가로로 두 번 자를 수 있기 때문입니다.

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

• p :=10^9 + 7
• m :=행렬의 행 개수, n :=행렬의 열 개수
• count :=빈 지도
• m - 1에서 0 사이의 i에 대해
  • n - 1에서 0 사이의 j에 대해 다음을 수행합니다.
    • counts[i, j] :=counts[i + 1, j] + counts[(i, j + 1) ] - counts[(i + 1, j + 1) ] + 행렬[i, j]
• f() 함수를 정의합니다. x, y, c
가 필요합니다.
• count :=counts[x, y]
• c가 0과 같으면
  • 카운트할 때 1 반환> 그렇지 않으면 0
• ans :=0
• x + 1 ~ m - 1 범위의 i에 대해
  • 0
  • ans :=ans + f(i, y, c - 1)

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

예시

from collections import defaultdict
class Solution:
   def solve(self, matrix, k):
      p = 10 ** 9 + 7

      m, n = len(matrix), len(matrix[0])
      counts = defaultdict(int)
      for i in range(m)[::-1]:
         for j in range(n)[::-1]:
            counts[(i, j)] = (counts[(i + 1, j)] + counts[(i, j + 1)] - counts[(i + 1, j + 1)] + matrix[i][j])

      def f(x, y, c):
         count = counts[(x, y)]
         if c == 0:
            return 1 if count > 0 else 0

         ans = 0
         for i in range(x + 1, m):
            if 0 < counts[(i, y)] < count:
               ans += f(i, y, c - 1)
         for j in range(y + 1, n):
            if 0 < counts[(x, j)] < count:
               ans += f(x, j, c - 1)

         return ans % p
      return f(0, 0, k - 1)
     
ob = Solution()
matrix = [
   [1, 1, 0],
   [1, 0, 1],
   [1, 1, 1],
]
k = 2
print(ob.solve(matrix, k))

입력

[  
[1, 1, 0],  
[1, 0, 1],  
[1, 1, 1]
], 2

출력

4