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
| class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = size(matrix), n = size(matrix[0]);
int res = 0;
f.resize(m, vector<int>(n));
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
res = max(res, dfs(matrix, r, c, -1));
}
}
return res;
}
int dfs(vector<vector<int>> &A, int r, int c, int prev) {
if (r < 0 || r >= m || c < 0 || c >= n || A[r][c] <= prev) return 0;
if (f[r][c] > 0) return f[r][c];
int res = 1;
for (int i = 0; i < 4; ++i) {
res = max(res, dfs(A, r + dr[i], c + dc[i], A[r][c]) + 1);
}
return f[r][c] = res;
}
int m, n, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<vector<int>> f;
};
|