# Share my DFS solution

• The solution is very straightforward. I use a boolean[][] to mark whether a cell has been visited or not.

``````public class Solution {
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
if(m == 0)  return 0;
int n = matrix[0].length;
if(n == 0)  return 0;
int[][] res = new int[m][n];
boolean[][] visited = new boolean[m][n];
int max = 1;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
max = Math.max(max, dfs(matrix, i, j, visited, res));
}
}
return max;
}
public int dfs(int[][] matrix, int i, int j, boolean[][] visited, int[][] res) {
int m = matrix.length, n = matrix[0].length;
if(visited[i][j])   return res[i][j];
int max = 1;
for(int[] dir : dirs) {
int row = i + dir[0];
int col = j + dir[1];
if(row >= 0 && row < m && col >= 0 && col < n && matrix[i][j] < matrix[row][col]) {
if(visited[row][col]) {
max = Math.max(max, 1 + res[row][col]);
} else {
max = Math.max(max, 1 + dfs(matrix, row, col, visited, res));
}
}
}
visited[i][j] = true;
res[i][j] = max;
return res[i][j];
}
}
``````

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