# Simple DFS solution

• `````` int longestIncreasingPath(vector<vector<int>>& matrix) {

if (matrix.empty())
return 0;

int N = matrix.size();
int M = matrix[0].size();

vector<vector<int>> lengths(N, vector<int>(M,1));

int localmax = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (!lengths[i][j]==0)
{
localmax = max(localmax, dfs(matrix, lengths, i, j, N, M));
}
}
}

return localmax;
}

int dfs(vector<vector<int>> & matrix,
vector<vector<int>> & lengths,
int i, int j, int N, int M)
{
if (lengths[i][j] > 1)
return lengths[i][j];

if (i+1 < N && matrix[i][j] > matrix[i+1][j])
{
lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i+1, j, N, M)+1);
}
if (j+1 < M && matrix[i][j] > matrix[i][j+1])
{
lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i, j+1, N, M)+1);
}
if (i-1 >= 0 && matrix[i][j] > matrix[i-1][j])
{
lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i-1, j, N, M)+1);
}
if (j-1>= 0 && matrix[i][j] > matrix[i][j-1])
{
lengths[i][j] = max(lengths[i][j], dfs(matrix, lengths, i, j-1, N, M)+1);
}
return lengths[i][j];
}
``````

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