Share my DFS solution


  • 0

    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];
        }
    }
    

Log in to reply
 

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