# C++_DFS_(Backtracking)_56ms_88.33%

• At first I use the backtracking method and got the TLE result. The reason is that we have made lots of unnecessary compare and finding. For a certain factor matrix[i][j], we can use a vector to store the longest path which through this factor, on the other hand, this can also help us to avoid duplicate finding in this factor.

Updated code (Accepted):

``````class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.empty()) return 0;

int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> check(m,vector<int>(n,0));
int res = 1;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
res = max(res, find(matrix, m, n, i, j, check));
}
}
return res;
}

int find(vector<vector<int>>& matrix, int m, int n, int row, int col, vector<vector<int>>& check){
int maxlen = check[row][col];
if(check[row][col] > 0){return maxlen;}
if(check[row][col]< INT_MAX){
if(row > 0 && matrix[row - 1][col] > matrix[row][col]){maxlen = max(find(matrix, m, n, row - 1, col,check),maxlen);}//up
if(row < m - 1 && matrix[row + 1][col] > matrix[row][col]){maxlen = max(find(matrix, m, n,  row + 1, col,check),maxlen);}//down
if(col > 0 && matrix[row][col - 1] > matrix[row][col]){maxlen = max(find(matrix, m, n, row, col - 1,check),maxlen);}//left
if(col < n - 1 && matrix[row][col + 1] > matrix[row][col]){maxlen = max(find(matrix, m, n, row, col + 1,check),maxlen);}//right
check[row][col] = ++maxlen;
}
return maxlen;
}
};
``````

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