# C++, 60ms, DFS solution

• The key of the problem is to save intermediate results.

``````class Solution {
public:
int check(vector<vector<int>>& matrix,vector<vector<int>>& res,int rsz, int csz, int i,int j){
if (res[i][j]>0) return res[i][j];   //already checked, just return the value
int curLen = 1;
if (i>0 && matrix[i-1][j]>matrix[i][j])
curLen=max(curLen,1+check(matrix,res,rsz,csz,i-1,j));
if (i<rsz-1 && matrix[i+1][j]>matrix[i][j])
curLen=max(curLen,1+check(matrix,res,rsz,csz,i+1,j));
if (j>0 && matrix[i][j-1]>matrix[i][j])
curLen=max(curLen,1+check(matrix,res,rsz,csz,i,j-1));
if (j<csz-1 && matrix[i][j+1]>matrix[i][j])
curLen=max(curLen,1+check(matrix,res,rsz,csz,i,j+1));
res[i][j]=curLen;
return curLen;
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty()||matrix[0].empty()) return 0;
int rsz = matrix.size();
int csz = matrix[0].size();
vector<vector<int>> res(rsz,vector<int> (csz,-1));
int maxLen = 1,curLen;
for (int i=0;i<rsz;i++)
for (int j=0;j<csz;j++){
curLen = check(matrix,res,rsz,csz,i,j);
maxLen = max(maxLen,curLen);
}
return maxLen;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.