#1444

Number of Ways of Cutting a Pizza

expert · 1145 · lc hard +32 · verified · 61.6% accepted · 1,907 likes · top 62%

Description

A rectangular pizza is represented as a rows x cols matrix where each cell is either 'A' (an apple) or '.' (empty). You must slice the pizza into exactly k pieces using k-1 straight cuts.

Each cut is either horizontal or vertical: a horizontal cut gives the top portion to one person, a vertical cut gives the left portion. The final remaining piece goes to the last person.

Return the number of distinct cutting sequences in which every piece contains at least one apple. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3

Output: 3

Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3

Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1

Output: 1

Code

1

2

3

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:

class Solution:
    def ways(self, pizza: List[str], k: int) -> int: