Package g1401_1500.s1444_number_of_ways_of_cutting_a_pizza

Class Solution

java.lang.Object

g1401_1500.s1444_number_of_ways_of_cutting_a_pizza.Solution

public class Solution
extends Object

1444 - Number of Ways of Cutting a Pizza.<p>Hard</p> <p>Given a rectangular pizza represented as a <code>rows x cols</code> matrix containing the following characters: <code>'A'</code> (an apple) and <code>'.'</code> (empty cell) and given the integer <code>k</code>. You have to cut the pizza into <code>k</code> pieces using <code>k-1</code> cuts.</p> <p>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.</p> <p>_Return the number of ways of cutting the pizza such that each piece contains <strong>at least</strong> one apple. _Since the answer can be a huge number, return this modulo 10^9 + 7.</p> <p><strong>Example 1:</strong></p> <p><strong><img src="https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png" alt="" /></strong></p> <p><strong>Input:</strong> pizza = [&ldquo;A..&rdquo;,&ldquo;AAA&rdquo;,&ldquo;&hellip;&rdquo;], k = 3</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> pizza = [&ldquo;A..&rdquo;,&ldquo;AA.&rdquo;,&ldquo;&hellip;&rdquo;], k = 3</p> <p><strong>Output:</strong> 1</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> pizza = [&ldquo;A..&rdquo;,&ldquo;A..&rdquo;,&ldquo;&hellip;&rdquo;], k = 1</p> <p><strong>Output:</strong> 1</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= rows, cols <= 50</code></li> <li><code>rows == pizza.length</code></li> <li><code>cols == pizza[i].length</code></li> <li><code>1 <= k <= 10</code></li> <li><code>pizza</code> consists of characters <code>'A'</code> and <code>'.'</code> only.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	ways(String[] pizza, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

ways

public int ways(String[] pizza,
 int k)