Chương trình đếm có bao nhiêu cách chúng ta có thể cắt ma trận thành k mảnh trong python

Giả sử chúng ta có một ma trận nhị phân và một giá trị khác k. Bạn muốn chia ma trận thành k phần sao cho mỗi phần chứa ít nhất một trong đó. Nhưng có một số quy tắc để cắt, chúng ta phải tuân theo thứ tự:1. Chọn một hướng:dọc hoặc ngang 2. Chọn một chỉ số trong ma trận để cắt thành hai phần. 3. Nếu chúng ta cắt theo chiều dọc, chúng ta không thể cắt phần bên trái được nữa mà chỉ có thể tiếp tục cắt phần bên phải. 4. Nếu chúng ta cắt theo chiều ngang, chúng ta không thể cắt phần trên được nữa và chỉ có thể tiếp tục cắt phần dưới cùng. Vì vậy chúng ta phải tìm số cách khác nhau để chia ma trận. Nếu câu trả lời rất lớn, hãy trả về kết quả mod (10 ^ 9 + 7).

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

k =2, thì đầu ra sẽ là 4, vì chúng ta có thể cắt theo chiều dọc hai lần và theo chiều ngang hai lần.

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

• p:=10 ^ 9 + 7
• m:=số hàng của ma trận, n:=số cột của ma trận
• counts:=một bản đồ trống
• đối với tôi trong phạm vi m - 1 đến 0, thực hiện
  • đối với j trong phạm vi n - 1 đến 0, thực hiện
    • counts [i, j]:=counts [i + 1, j] + counts [(i, j + 1)] - counts [(i + 1, j + 1)] + ma trận [i, j]
• Định nghĩa một hàm f (). Điều này sẽ lấy x, y, c
• count:=counts [x, y]
• nếu c giống 0, thì
  • trả về 1 khi số đếm> 0, nếu không thì 0
• ans:=0
• đối với tôi trong phạm vi x + 1 đến m - 1, thực hiện
  • if 0
  • ans:=ans + f (i, y, c - 1)

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

Ví dụ

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

Đầu vào

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

Đầu ra

4