// 1444. Number of Ways of Cutting a Pizza #include "leetcode.h" /* * given rectangular pizza represented as a rows x cols matrix containing the * following characters 'A' an apple and '.' empty cell, and given integer 'k'. * you have to cut the pizza into 'k' pieces using 'k - 1' cuts. */ class Solution { void add(long &a, long &b) { a = (a + b) % ((int)1e9 + 7); } public: int ways(vector &pizza, int k) { int m = pizza.size(), n = pizza[0].size(); vvd(int) cnt(m + 1, vector(n + 1)); for (int i = m - 1; i >= 0; --i) { int s = 0; for (int j = n - 1; j >= 0; --j) { s += pizza[i][j] == 'A'; cnt[i][j] = cnt[i + 1][j] + s; } } vvd(vector) dp(m + 1, vvd(long)(n + 1, vector(k + 1))); for (int i = m - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { dp[i][j][1] = cnt[i][j] > 0; for (int p = 2; p <= k; ++p) { for (int q = i + 1; q < m; ++q) { if (cnt[i][j] == cnt[q][j]) continue; if (cnt[q][j] == 0) break; add(dp[i][j][p], dp[q][j][p - 1]); } for (int q = j + 1; q < n; ++q) { if (cnt[i][j] == cnt[i][q]) continue; if (cnt[i][q] == 0) break; add(dp[i][j][p], dp[i][q][p - 1]); } } } } return dp[0][0][k]; } }; int main() { Solution obj; vector p1 = {"A..", "AAA", "..."}; vector p2 = {"A..", "AA.", "..."}; vector p3 = {"A..", "A..", "..."}; printf("%d\n", obj.ways(p1, 3)); // expect: 3 printf("%d\n", obj.ways(p2, 3)); // expect: 1 printf("%d\n", obj.ways(p3, 1)); // expect: 1 }