程序计算在python中将矩阵切成k片的数量方法
假设我们有一个二进制矩阵和另一个值k。您希望将矩阵拆分为k个片段,以便每个片段中至少包含一个1。但是有一些剪切规则,我们必须按顺序进行:1.选择一个方向:垂直或水平。2.在矩阵中选择一个索引以剪切为两个部分。3.如果垂直切割,我们将无法再切割左侧部分,而只能继续切割右侧部分。4.如果我们水平切割,我们将无法再切割顶部,而只能继续切割底部。因此,我们必须找到划分矩阵的不同方法。如果答案很大,则返回结果mod(10^9+7)。
所以,如果输入像
k=2,则输出将为4,因为我们可以垂直切两次和水平切两次。
为了解决这个问题,我们将遵循以下步骤-
p:=10^9+7
m:=矩阵的行数,n:=矩阵的列数
计数:=一个空的映射
对于范围在m-1到0的i
counts[i,j]:=counts[i+1,j]+counts[(i,j+1)]-counts[(i+1,j+1)]+矩阵[i,j]
对于范围n-1到0的j,执行
定义一个功能f()
。这将需要x,y,c
计数:=计数[x,y]
如果c与0相同,则
当count>0时返回1,否则返回0
回答:=0
对于x范围从+1到m-1的i
ans:=ans+f(i,y,c-1)
如果0<counts[(i,y)]<count,则
对于y+1到n-1范围内的j
ans:=ans+f(x,j,c-1)
如果0<counts[(x,j)]<count,则
返回ansmodp
从主方法调用并返回f(0,0,k-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