题解 | 矩阵最长递增路径

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    int m = 0;
    int n = 0;
    int maxDistance = 0;

    public int solve (int[][] matrix) {
        // write code here
        m = matrix.length;
        n = matrix[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                //遍历每个点 看看能走到的最长路径
                int distance = dfs(i, j, matrix, -1);
                maxDistance = Math.max(maxDistance, distance);
            }
        }        
        return maxDistance;
        
    }

    private int dfs(int i, int j, int[][] matrix,  int pre) {
        if (pre >= matrix[i][j]) return 0;
        int distance = 1;
        int up = 0;
        int down = 0;
        int left = 0;
        int right = 0;
        if (i + 1 < m && matrix[i][j] < matrix[i+1][j]) {
            down = dfs(i+1, j, matrix, matrix[i][j]); //下走的路径长度
           
        }
        if (i - 1 >= 0 && matrix[i][j] < matrix[i-1][j] ) {
            up = dfs(i-1, j, matrix, matrix[i][j]); //上走的路径长度
        }
        if (j + 1 < n && matrix[i][j] < matrix[i][j+1] ) {
            right = dfs(i, j+1, matrix, matrix[i][j]); // 右走的路径长度
            
        }
        if (j - 1 >= 0 && matrix[i][j] < matrix[i][j-1]) { 
            left = dfs(i, j-1, matrix, matrix[i][j]); // 左走的路径长度
        }
        
        return distance + Math.max(up, Math.max(down, Math.max(left, right))); // 取最长的路径+1
        
    }
}