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

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    int max = 0;//存放结果————最长路径的长度
    ArrayList<Integer> list = new ArrayList<>();//存放一条路径中的元素
    private void Helper(int[][] matrix,int i,int j,boolean[][] used){
        //把当前位置的元素放入到列表中，并把对应的used数组元素置为true，
        //used[i][j]为true表示当前元素已经被使用了，不能被重复使用了
        used[i][j] = true;
        list.add(matrix[i][j]);
        //递归搜索上下左右四个方向
        //搜索之前需要判断坐标合法性，是否递增，元素是否已经被使用过
        if(i - 1 >= 0 && matrix[i-1][j] > matrix[i][j] && !used[i-1][j]){
            Helper(matrix,i-1,j,used);
        }
        if(i + 1 < matrix.length && matrix[i+1][j] > matrix[i][j] && !used[i+1][j]){
            Helper(matrix,i+1,j,used);
        }        
        if(j - 1 >= 0 && matrix[i][j-1] > matrix[i][j] && !used[i][j-1]){
            Helper(matrix,i,j-1,used);
        }        
        if(j + 1 < matrix[i].length && matrix[i][j+1] > matrix[i][j] && !used[i][j+1]){
            Helper(matrix,i,j+1,used);
        }
        //四个方向都搜索完了，说明这条路径已经到了终点：没有合法坐标或者四个方向没有递增的元素
        //判断这条路径长度是否大于max
        int size = list.size();
        if(size > max){
            max = size;
        }
        //回退，删除列表中的当前元素，并把used数组中的当前元素置为false
        list.remove(size-1);
        used[i][j] = false;
    }
    public int solve (int[][] matrix) {
        // write code here
        int row = matrix.length;//matrix数组的行
        int col = matrix[0].length;//matrix数组的列
        boolean[][] used = new boolean[row][col];//用来标记matrix数组中的某个元素是否被使用过
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //路径的入口不一定只是从左上角开始，可以是从任意元素开始
                Helper(matrix,i,j,used);
            }
        }
        return max;
    }
}