题解 | #矩阵最长递增路径#
矩阵最长递增路径
https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2
class Solution {
public:
bool isBound(int x, int y, int n, int m) {
if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
return false;
}
return true;
}
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int recursion(int x, int y, vector<vector<int> >& matrix,
vector<vector<int>>& mark) {
if (mark[x][y] != 0)
return mark[x][y];
int cmax = 0;
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (isBound(tx, ty, matrix.size(), matrix[0].size())) {
if (matrix[x][y] < matrix[tx][ty]) {
cmax = max(cmax, recursion(tx, ty, matrix, mark));
recursion(tx, ty, matrix, mark);
}
}
}
mark[x][y] = cmax + 1;
return cmax + 1;
}
int solve(vector<vector<int> >& matrix) {
// write code here
int max = 0;
vector<vector<int>> mark(matrix.size(), vector<int> (matrix[0].size(), 0));
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
if (recursion(i, j, matrix, mark) > max) {
max = recursion(i, j, matrix, mark);
}
}
}
return max;
}
};
