题解 | 矩阵最长递增路径

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    static   public int solve (int[][] matrix) {
        int[][] visited = new int[matrix.length][matrix[0].length];
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        queue.add(1);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                list.add(matrix[i][j]);
                visited[i][j] = 1;
                dfs(matrix, visited, i, j, matrix[i][j], queue, list);
                visited[i][j] = 0;
                list.remove(list.size() - 1);
            }
        }
        return queue.poll();
    }

    static  public void dfs(int[][] matrix, int[][] v, int x, int y, int value,
                            PriorityQueue<Integer> queue, List<Integer> list) {

        if (!queue.isEmpty()) {
            Integer peek = queue.peek();
            if (peek < list.size()) {
                queue.poll();
                queue.add(list.size());
            }
        }
        //往左边走
        if (x - 1 >= 0 && v[x - 1][y] == 0 && matrix[x - 1][y] > value) {
            list.add(matrix[x - 1][y]);
            v[x - 1][y] = 1;
            dfs(matrix, v, x - 1, y, matrix[x - 1][y], queue, list);
            v[x - 1][y] = 0;
            list.remove(list.size() - 1);
        }
        //往右边走
        if (x + 1 < matrix.length && v[x + 1][y] == 0 && matrix[x + 1][y] > value) {
            list.add(matrix[x + 1][y]);
            v[x + 1][y] = 1;
            dfs(matrix, v, x + 1, y, matrix[x + 1][y], queue, list);
            v[x + 1][y] = 0;
            list.remove(list.size() - 1);
        }
        //往上走
        if (y - 1 >= 0 && v[x][y - 1] == 0 && matrix[x][y - 1] > value) {
            list.add(matrix[x][y - 1]);
            v[x][y - 1] = 1;
            dfs(matrix, v, x, y - 1, matrix[x][y - 1], queue, list);
            v[x][y - 1] = 0;
            list.remove(list.size() - 1);
        }

        if (y + 1 < matrix.length && v[x][y + 1] == 0 && matrix[x][y + 1] > value) {
            list.add(matrix[x][y + 1]);
            v[x][y + 1] = 1;
            dfs(matrix, v, x, y + 1, matrix[x][y + 1], queue, list);
            v[x][y + 1] = 0;
            list.remove(list.size() - 1);
        }
    }
}