1444. Number of Ways of Cutting a Pizza¶
题目信息¶
- 题号:
1444
- 难度:
Hard
- 主题:
动态规划、二维前缀和、切割计数
- 原题:
- 重点:
用
k-1次水平或竖直切割得到k块,每次交出上方或左方部分,最终每块至少含一个苹果
题目重述¶
给定字符矩阵 pizza,A 表示苹果,. 表示空格。需要进行 k-1 次切割,把披萨分成 k 块。
每次可以沿格子边界水平切割并交出上方部分,或竖直切割并交出左方部分,继续切割剩余部分。要求最终每块至少含一个苹果。请返回合法切割顺序数量对 10^9 + 7 取模后的结果。
1 <= pizza.length, pizza[i].length <= 50,1 <= k <= 10。
自建示例¶
水平和竖直切割都可能合法:
输入:pizza = ["A.","AA"], k = 2
输出:2
解释:沿两行之间水平切割,或沿两列之间竖直切割,得到的两块都含苹果。
苹果数量少于块数时无解:
输入:pizza = ["A"], k = 2
输出:0
解释:唯一苹果不能同时分配到两块披萨中。