题解 | #矩阵最长递增路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
     int count = 0;
    public int solve (int[][] matrix) {
        // write code here
        for (int i = 0; i < matrix.length; i++) {
            for (int t = 0; t < matrix[0].length; t++) {
                dfs(matrix, 1, i, t);
            }
        }
        return count;
    }

    public void dfs(int[][] matrix, int depth, int n, int m) {
        int temp = matrix[n][m];
        //System.out.print("" + n + ":" + m +"||"+temp + "  ");
        if (!((n-1 >= 0 && matrix[n-1][m] > temp) || (m-1 >= 0 && matrix[n][m-1] > temp) || 
        (n+1 < matrix.length && matrix[n+1][m] > temp) || (m+1 < matrix[0].length && matrix[n][m+1] > temp))) {
            //System.out.print(" " + matrix[1][0] + " bingo ");
            if (count < depth) count = depth;
            return;
        }
        //上
        if (n-1 >= 0 && matrix[n-1][m] > temp) {
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n-1,m);
            matrix[n][m] = temp;
        }
        //左
        if (m-1 >= 0 && matrix[n][m-1] > temp) {
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n,m-1);
            matrix[n][m] = temp;
        }
        //下
        if (n+1 < matrix.length && matrix[n+1][m] > temp) {
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n+1,m);
            matrix[n][m] = temp;
        }
        //右
        if (m+1 < matrix[0].length && matrix[n][m+1] > temp){
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n,m+1);
            matrix[n][m] = temp;
        }
    }
}