leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2328.cpp (994B)

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