# My C++ DFS solution, store partial result

• ``````class Solution {
public:
int dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int i, int j, int m, int n) {
int left, right, up, down;
left = right = up = down = 0;

if(i >= 1 && matrix[i-1][j] > matrix[i][j])
up = visited[i-1][j] > 1 ? visited[i-1][j] : dfs(matrix, visited, i-1, j, m, n);

if(j >= 1 && matrix[i][j-1] > matrix[i][j])
left = visited[i][j-1] > 1 ? visited[i][j-1] : dfs(matrix, visited, i, j-1, m, n);

if(i < m-1 && matrix[i+1][j] > matrix[i][j])
down = visited[i+1][j] > 1 ? visited[i+1][j] : dfs(matrix, visited, i+1, j, m, n);

if(j < n-1 && matrix[i][j+1] > matrix[i][j])
right = visited[i][j+1] > 1 ? visited[i][j+1] : dfs(matrix, visited, i, j+1, m, n);

visited[i][j] = 1 + max(max(up, down), max(left, right));

return visited[i][j];
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
vector<vector<int>> visited (m, vector<int>(n, 1));
int result = 0;

for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
result = max(result, dfs(matrix, visited, i, j, m, n));
}
}
return result;
}
``````

};

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