class Solution {

    int m,n;
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int[][] mome;

    public int longestIncreasingPath(int[][] matrix) {
        int ret = 0;
        m = matrix.length;
        n = matrix[0].length;
        mome = new int[m][n];

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                ret = Math.max(ret, dfs(matrix,i,j));

        return ret;   

    }

    private int dfs(int[][] matrix, int i, int j){
        if(mome[i][j] != 0)
            return mome[i][j];

        int ret = 1;//至少有一个最长递增路径

        for(int k = 0; k < 4; k++){
            int x = i + dx[k], y = j + dy[k];
            
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                ret = Math.max(ret, dfs(matrix,x,y)+1);//注意进去第一个位置满足条件也算递增路径
            }
        }

        mome[i][j] = ret;
        return mome[i][j];
    }

}