<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 {
public:
    const int MOD = 1e9+7;
    int m, n;
    vector<vector<int>> sum;
    
    // 查询 (r1, c1) 到 (r2, c2) 矩形区域的苹果数量
    int query(int r1, int c1, int r2, int c2) {
        return sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
    }

    int memo[15][55][55]; // 记忆化数组
    
    int dfs(int c, int i, int j) {
        if (c == 0) {
            return query(i, j, m, n) > 0 ? 1 : 0;  // 剩余矩阵是否有苹果
        }
        if (memo[c][i][j] != -1) return memo[c][i][j];  // 返回缓存结果
        int res = 0;

        // 水平切割
        for (int j2 = j + 1; j2 < n; j2++) {
            if (query(i, j, m, j2) > 0) {  // 确保能切割出含有苹果的部分
                res = (res + dfs(c - 1, i, j2)) % MOD;
            }
        }

        // 垂直切割
        for (int i2 = i + 1; i2 < m; i2++) {
            if (query(i, j, i2, n) > 0) {  // 确保能切割出含有苹果的部分
                res = (res + dfs(c - 1, i2, j)) % MOD;
            }
        }

        memo[c][i][j] = res;  // 记忆化存储
        return res;
    }

    int ways(vector<string>& pizza, int k) {
        m = pizza.size();
        n = pizza[0].size();
        sum.resize(m + 1, vector<int>(n + 1, 0));
        memset(memo, -1, sizeof(memo));

        // 构建二维前缀和
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (pizza[i][j] == 'A' ? 1 : 0);
            }
        }

        return dfs(k - 1, 0, 0);
    }
};

9500