leetcode

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

2328.cpp (994B)

      1 class Solution {
      2     int MOD = 1E9 + 7;
      3     int dp[1001][1001];
      4 
      5     int n, m;
      6     bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
      7 
      8     int rec(const vector<vector<int>> &grid, int i, int j) {
      9         if (dp[i][j] != -1) return dp[i][j];
     10 
     11         static const int offs_x[4] = {0, 0, 1, -1};
     12         static const int offs_y[4] = {1, -1, 0, 0};
     13 
     14         int res = 0;
     15         for (int k = 0; k < 4; k++) {
     16             int x = i + offs_x[k], y = j + offs_y[k];
     17             if (!valid(x, y)) continue;
     18             if (grid[i][j] < grid[x][y]) res = (res + rec(grid, x, y) + 1) % MOD;
     19         }
     20         return dp[i][j] = res;
     21     }
     22 
     23   public:
     24     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     25     int countPaths(const vector<vector<int>> &grid) {
     26         n = grid.size(), m = grid[0].size();
     27 
     28         int res = m * n;
     29         for (int i = 0; i < n; i++)
     30             for (int j = 0; j < m; j++)
     31                 res = (res + rec(grid, i, j)) % MOD;
     32 
     33         return res;
     34     }
     35 };