<p>Given a rectangular pizza represented as a <code>rows x cols</code>&nbsp;matrix containing the following characters: <code>&#39;A&#39;</code> (an apple) and <code>&#39;.&#39;</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.&nbsp;</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><em>Return the number of ways of cutting the pizza such that each piece contains <strong>at least</strong> one apple.&nbsp;</em>Since the answer can be a huge number, return this modulo 10^9 + 7.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png" style="width: 500px; height: 378px;" /></strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;AAA&quot;,&quot;...&quot;], k = 3
<strong>Output:</strong> 3 
<strong>Explanation:</strong> The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;AA.&quot;,&quot;...&quot;], k = 3
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;A..&quot;,&quot;...&quot;], k = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rows, cols &lt;= 50</code></li>
	<li><code>rows ==&nbsp;pizza.length</code></li>
	<li><code>cols ==&nbsp;pizza[i].length</code></li>
	<li><code>1 &lt;= k &lt;= 10</code></li>
	<li><code>pizza</code> consists of characters <code>&#39;A&#39;</code>&nbsp;and <code>&#39;.&#39;</code> only.</li>
</ul>

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

        # Need a solution map. Key -> K + state, Value -> Number of valid cuts
        # Q1: How do we store the state?
        # Q2: How do we iterate through the cuts?
        #
        # k = 1 + [".", ".", "."] -> 0
        # k = 1 + ["A", ".", "."] -> 1
        #
        sol_map = {}

        def validate(pizza):
            for row in range(len(pizza)):
                for col in range(len(pizza[0])):
                    if pizza[row][col] == 'A':
                        return True

        def count(pizza):
            count = 0
            for row in range(len(pizza)):
                for col in range(len(pizza[0])):
                    if pizza[row][col] == 'A':
                        count +=1
            return count

        def evaluate(sol_map, pizza, k) -> int:

            key = ' '.join(pizza) + str(k)
            if sol_map.get(key) is not None:
                return sol_map[key]

            # size 1 condition
            if k == 1:
                if validate(pizza):
                    sol_map[key] = 1
                    return 1
                else:
                    sol_map[key] = 0
                    return 0

            # Need to validate that cut that is being done has an apple

            if count(pizza) < k:
                return 0

            # slice horizontally
            possible_hor_cuts = 0
            for i in range(len(pizza) - 1):

                # Need to check if this has an apple
                if validate(pizza[0:i + 1]):
                    possible_hor_cuts += evaluate(sol_map, pizza[i + 1:], k - 1)  # Might need to double-check

            # slice vertically
            possible_vert_cuts = 0
            for i in range(len(pizza[0]) - 1):

                if validate([x[0:i + 1] for x in pizza]):
                    possible_vert_cuts += evaluate(sol_map, [x[i + 1:] for x in pizza], k - 1)

            sol_map[key] = possible_hor_cuts + possible_vert_cuts
            return possible_hor_cuts + possible_vert_cuts

        return evaluate(sol_map, pizza, k) % 1000000007

28100