1444. Number of Ways of Cutting a Pizza

Hard

1.6K

90

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 you choose the direction: vertical or horizontal, then you 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 this modulo 10^9 + 7.

**Example 1:**

Input:pizza = ["A..","AAA","..."], k = 3Output:3Explanation: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 = 3Output:1

**Example 3:**

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

**Constraints:**

`1 <= rows, cols <= 50`

`rows == pizza.length`

`cols == pizza[i].length`

`1 <= k <= 10`

`pizza`

consists of characters`'A'`

and`'.'`

only.

Accepted

61.8K

Submissions

97.1K

Acceptance Rate

63.7%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved