DFS Java Simple Solution


  • 0
    C
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix.length==0)return 0;
            int[][] records=new int[matrix.length][matrix[0].length];
            int res=0;
            for(int i=0;i<matrix.length;i++){
                for(int j=0;j<matrix[0].length;j++){
                    if(records[i][j]==0){
                        records[i][j]=dfs(records,matrix,i,j);
                        res=Math.max(res,records[i][j]);
                    }
                }
            }
            return res;
      
        }
        
        int dfs(int[][] records,int[][] matrix,int i,int j){
            int res=1;
            if(i>0&&matrix[i-1][j]<matrix[i][j]){
                if(records[i-1][j]>0) res=Math.max(res,1+records[i-1][j]);
                else res=Math.max(res,1+dfs(records,matrix,i-1,j));
            }
            if(i<matrix.length-1 && matrix[i+1][j]<matrix[i][j]){
                if(records[i+1][j]>0) res=Math.max(res,1+records[i+1][j]);
                else res=Math.max(res,1+dfs(records,matrix,i+1,j));
            }
            if(j<matrix[0].length-1 && matrix[i][j+1]<matrix[i][j]){
                if(records[i][j+1]>0) res=Math.max(res,1+records[i][j+1]);
                else res=Math.max(res,1+dfs(records,matrix,i,j+1));
            }
            if(j>0 && matrix[i][j-1]<matrix[i][j]){
                if(records[i][j-1]>0) res=Math.max(res,1+records[i][j-1]);
                else res=Math.max(res,1+dfs(records,matrix,i,j-1));
            }
            
            return res;
        }
    }
    

Log in to reply
 

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