1444. Number of Ways of Cutting a Pizza Hard

1/**
2 * [1444] Number of Ways of Cutting a Pizza
3 *
4 * 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. 
5 * 
6 * 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.
7 * 
8 * 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.
9 * 
10 *  
11 * Example 1:
12 * 
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png" style="width: 500px; height: 378px;" />
14 * 
15 * 
16 * Input: pizza = ["A..","AAA","..."], k = 3
17 * Output: 3 
18 * Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.
19 * 
20 * 
21 * Example 2:
22 * 
23 * 
24 * Input: pizza = ["A..","AA.","..."], k = 3
25 * Output: 1
26 * 
27 * 
28 * Example 3:
29 * 
30 * 
31 * Input: pizza = ["A..","A..","..."], k = 1
32 * Output: 1
33 * 
34 * 
35 *  
36 * Constraints:
37 * 
38 * 
39 * 	1 <= rows, cols <= 50
40 * 	rows == pizza.length
41 * 	cols == pizza[i].length
42 * 	1 <= k <= 10
43 * 	pizza consists of characters 'A' and '.' only.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/
49// discuss: https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn ways(pizza: Vec<String>, k: i32) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_1444() {
67    }
68}
69