Skip to content

1444. Number of Ways of Cutting a Pizza 👍

  • Time: $O(MNk \cdot (M + N))$
  • Space: $O(MNk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
 public:
  int ways(vector<string>& pizza, int k) {
    const int M = pizza.size();
    const int N = pizza[0].size();
    vector<vector<vector<int>>> mem(M,
                                    vector<vector<int>>(N, vector<int>(k, -1)));
    vector<vector<int>> prefix(M + 1, vector<int>(N + 1));

    for (int i = 0; i < M; ++i)
      for (int j = 0; j < N; ++j)
        prefix[i + 1][j + 1] = (pizza[i][j] == 'A') + prefix[i][j + 1] +
                               prefix[i + 1][j] - prefix[i][j];

    return ways(0, 0, k - 1, M, N, prefix, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of ways to cut pizza[m..M)[n..N) with k cuts.
  int ways(int m, int n, int k, const int M, const int N,
           const vector<vector<int>>& prefix,
           vector<vector<vector<int>>>& mem) {
    if (k == 0)
      return hasApple(prefix, m, M, n, N) ? 1 : 0;
    if (mem[m][n][k] != -1)
      return mem[m][n][k];

    mem[m][n][k] = 0;

    for (int i = m + 1; i < M; ++i)  // Cut horizontally.
      if (hasApple(prefix, m, i, n, N) && hasApple(prefix, i, M, n, N)) {
        mem[m][n][k] += ways(i, n, k - 1, M, N, prefix, mem);
        mem[m][n][k] %= kMod;
      }

    for (int j = n + 1; j < N; ++j)  // Cut vertically.
      if (hasApple(prefix, m, M, n, j) && hasApple(prefix, m, M, j, N)) {
        mem[m][n][k] += ways(m, j, k - 1, M, N, prefix, mem);
        mem[m][n][k] %= kMod;
      }

    return mem[m][n][k];
  }

  // Returns true if pizza[row1..row2)[col1..col2) has apple.
  bool hasApple(const vector<vector<int>>& prefix, int row1, int row2, int col1,
                int col2) {
    return (prefix[row2][col2] - prefix[row1][col2] -  //
            prefix[row2][col1] + prefix[row1][col1]) > 0;
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
  public int ways(String[] pizza, int k) {
    final int M = pizza.size();
    final int N = pizza[0].length();
    int[][][] mem = new int[M][N][k];
    int[][] prefix = new int[M + 1][N + 1];

    for (int[][] A : mem)
      Arrays.stream(mem).forEach(B -> Arrays.fill(B, -1));

    for (int i = 0; i < M; ++i)
      for (int j = 0; j < N; ++j)
        prefix[i + 1][j + 1] = (pizza[i].charAt(j) == 'A' ? 1 : 0) + prefix[i][j + 1] +
                               prefix[i + 1][j] - prefix[i][j];

    return ways(0, 0, k - 1, M, N, prefix, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of ways to cut pizza[m..M)[n..N) with k cuts.
  private int ways(int m, int n, int k, int M, int N, int[][] prefix, int[][][] mem) {
    if (k == 0)
      return hasApple(prefix, m, M, n, N) ? 1 : 0;
    if (mem[m][n][k] != -1)
      return mem[m][n][k];

    mem[m][n][k] = 0;

    for (int i = m + 1; i < M; ++i) // Cut horizontally.
      if (hasApple(prefix, m, i, n, N) && hasApple(prefix, i, M, n, N)) {
        mem[m][n][k] += ways(i, n, k - 1, M, N, prefix, mem);
        mem[m][n][k] %= kMod;
      }

    for (int j = n + 1; j < N; ++j) // Cut vertically.
      if (hasApple(prefix, m, M, n, j) && hasApple(prefix, m, M, j, N)) {
        mem[m][n][k] += ways(m, j, k - 1, M, N, prefix, mem);
        mem[m][n][k] %= kMod;
      }

    return mem[m][n][k];
  }

  // Returns true if pizza[row1..row2)[col1..col2) has apple.
  private boolean hasApple(int[][] prefix, int row1, int row2, int col1, int col2) {
    return (prefix[row2][col2] - prefix[row1][col2] - //
            prefix[row2][col1] + prefix[row1][col1]) > 0;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
  def ways(self, pizza: list[str], k: int) -> int:
    kMod = 1_000_000_007
    M = len(pizza)
    N = len(pizza[0])
    prefix = [[0] * (N + 1) for _ in range(M + 1)]

    for i in range(M):
      for j in range(N):
        prefix[i + 1][j + 1] = ((pizza[i][j] == 'A') + prefix[i][j + 1] +
                                prefix[i + 1][j] - prefix[i][j])

    def hasApple(row1: int, row2: int, col1: int, col2: int) -> bool:
      """Returns True if pizza[row1..row2)[col1..col2) has apple."""
      return (prefix[row2][col2] - prefix[row1][col2] -
              prefix[row2][col1] + prefix[row1][col1]) > 0

    @functools.lru_cache(None)
    def dp(m: int, n: int, k: int) -> int:
      """Returns the number of ways to cut pizza[m..M)[n..N) with k cuts."""
      if k == 0:
        return 1 if hasApple(m, M, n, N) else 0

      res = 0

      for i in range(m + 1, M):  # Cut horizontally.
        if hasApple(m, i, n, N) and hasApple(i, M, n, N):
          res += dp(i, n, k - 1)

      for j in range(n + 1, N):  # Cut vertically.
        if hasApple(m, M, n, j) and hasApple(m, M, j, N):
          res += dp(m, j, k - 1)

      return res % kMod

    return dp(0, 0, k - 1)