leetcode

0 class Solution {

1 int n, m, mod = 1e9 + 7;

2 vector<vector<int>> count;

3 vector<vector<vector<int>>> dp = vector(10, vector(50, vector(50, -1)));

4

5 int rec(int row, int col, int left) {

6 if (count[row][col] == 0) return 0;

7 if (left == 0) return 1;

8 if (dp[left][row][col] != -1) return dp[left][row][col];

9

10 int &res = dp[left][row][col] = 0;

11 for (int i = row; i < n - 1; i++) {

12 if (count[row][col] - count[i + 1][col] <= 0) continue;

13 res = (res + rec(i + 1, col, left - 1)) % mod;

14 }

15

16 for (int i = col; i < m - 1; i++) {

17 if (count[row][col] - count[row][i + 1] <= 0) continue;

18 res = (res + rec(row, i + 1, left - 1)) % mod;

19 }

20

21 return res;

22 }

23

24 public:

25 int ways(vector<string> &pizza, int k) {

26 n = pizza.size(), m = pizza[0].size();

27 count = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));

28

29 for (int i = n - 1; i >= 0; i--)

30 for (int j = m - 1; j >= 0; j--)

31 count[i][j] = count[i + 1][j] + count[i][j + 1] - count[i + 1][j + 1] + (pizza[i][j] == 'A');

32

33 return rec(0, 0, k - 1);

34 }

35 };