leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1444.cpp (1183B)

      1 class Solution {
      2     int n, m, mod = 1e9 + 7;
      3     vector<vector<int>> count;
      4     vector<vector<vector<int>>> dp = vector(10, vector(50, vector(50, -1)));
      5 
      6     int rec(int row, int col, int left) {
      7         if (count[row][col] == 0) return 0;
      8         if (left == 0) return 1;
      9         if (dp[left][row][col] != -1) return dp[left][row][col];
     10 
     11         int &res = dp[left][row][col] = 0;
     12         for (int i = row; i < n - 1; i++) {
     13             if (count[row][col] - count[i + 1][col] <= 0) continue;
     14             res = (res + rec(i + 1, col, left - 1)) % mod;
     15         }
     16 
     17         for (int i = col; i < m - 1; i++) {
     18             if (count[row][col] - count[row][i + 1] <= 0) continue;
     19             res = (res + rec(row, i + 1, left - 1)) % mod;
     20         }
     21 
     22         return res;
     23     }
     24 
     25   public:
     26     int ways(vector<string> &pizza, int k) {
     27         n = pizza.size(), m = pizza[0].size();
     28         count = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
     29 
     30         for (int i = n - 1; i >= 0; i--)
     31             for (int j = m - 1; j >= 0; j--)
     32                 count[i][j] = count[i + 1][j] + count[i][j + 1] - count[i + 1][j + 1] + (pizza[i][j] == 'A');
     33 
     34         return rec(0, 0, k - 1);
     35     }
     36 };