Number of Ways of Cutting a Pizza
Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell), and given the integer k, you have to cut the pizza into k pieces using k - 1 cuts.
For each cut, choose the direction: vertical or horizontal. Then choose a cut position at the cell boundary and cut the pizza into two pieces.
- If you cut the pizza vertically, give the left part of the pizza to a person.
- If you cut the pizza horizontally, give the upper part of the pizza to a person.
- Give the last piece of pizza to the last person.
Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return it modulo 10^9 + 7.
Example 1
Input
pizza = ["A..","AAA","..."], k = 3Output
3The figure above shows the three ways to cut the pizza, and each piece contains at least one apple.
Example 2
Input
pizza = ["A..","AA.","..."], k = 3Output
1There is exactly one way to make two cuts so that all three resulting pieces contain at least one apple.
Constraints
- 1 <= rows, cols <= 50
- rows == pizza.length
- cols == pizza[i].length
- 1 <= k <= 10
- pizza consists of characters 'A' and '.' only.