1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
private final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
private int mod = 1000000007;
public int countPaths(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
long[][] cache = new long[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(matrix, i, j, cache);
}
}
long ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans += cache[i][j];
}
}
return (int) (ans % (mod));
}
private long dfs(int[][] matrix, int row, int col, long[][] cache) {
if (cache[row][col] != 0) {
return cache[row][col];
}
long numOfWays = 1;
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (!isOutOfBound(matrix.length, matrix[0].length, newRow, newCol)
&& matrix[row][col] < matrix[newRow][newCol]) {
numOfWays = (numOfWays + dfs(matrix, newRow, newCol, cache)) % mod;
}
}
cache[row][col] = numOfWays;
return cache[row][col];
}
private boolean isOutOfBound(int rowLength, int colLength, int row, int col) {
return row < 0 || row >= rowLength || col < 0 || col >= colLength;
}
}
|
