1444. Number of Ways of Cutting a Pizza

题目信息

题号:

1444

难度:

Hard

主题:

动态规划、二维前缀和、切割计数

原题:

LeetCode 1444

重点:

用 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
解释:唯一苹果不能同时分配到两块披萨中。