leetcode

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 };