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

import java.util.*;


public class Solution {
    // 自定义坐标信息结构类
    public class Info {
        public int x;
        public int y;
        public Info(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here

        // 算法思路：采用基于【地图标记】的【记忆化搜索】，整体可参考【岛屿问题】

        // 调用递归函数 - 遍历数组
        int[][] arrived = new int[matrix.length][matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (arrived[i][j] == 0) {
                    // 当前路径没有被访问过，则开启搜索
                    Info curInfo = new Info(i, j);
                    int result = process(matrix, arrived, curInfo);
                    if (result > max) {
                        max = result;
                    }
                }
            }
        }
        return max;
    }

    // 设计递归函数
    // 返回值：当前位置距离终点的路径长度（包含自身）
    // 参数：矩阵、已走过位置矩阵、当前位置
    public int process(int[][] matrix, int[][] arrived, Info curLocation) {
        // 记录当前位置
        int curX = curLocation.x;
        int curY = curLocation.y;
        int cur = matrix[curX][curY];
        int limitX = matrix.length;
        int limitY = matrix[0].length;

        // 设置一个可达坐标队列，记录当前位置可以走向的下一个位置
        Queue<Info> accessible = new LinkedList<>();
        // 上 - x-1
        if ((curX - 1) >= 0 && cur < matrix[curX - 1][curY]) {
            accessible.add(new Info(curX - 1, curY));
        }
        // 下 - x+1
        if ((curX + 1) < limitX && cur < matrix[curX + 1][curY]) {
            accessible.add(new Info(curX + 1, curY));
        }
        // 左 - y-1
        if ((curY - 1) >= 0 && cur < matrix[curX][curY - 1]) {
            accessible.add(new Info(curX, curY - 1));
        }
        // 右 - y+1
        if ((curY + 1) < limitY && cur < matrix[curX][curY + 1]) {
            accessible.add(new Info(curX, curY + 1));
        }

        // 递归出口
        if (accessible.size() == 0) {
            // 代表没办法接着走了，返回当前位置为路径中唯一的位置（1），并记录arrived
            arrived[curX][curY] = 1;
            return 1;
        }

        // 分支限界 - 记忆化搜索
        int maxLong = 0;
        for (Info next : accessible) {
            // 记忆化搜索 - 若next位置在arrived有记录则直接采用记录即可
            int pathLong = 0;
            if (arrived[next.x][next.y] > 0) {
                pathLong = arrived[next.x][next.y];
            } else {
                // 否则记录调用递归
                pathLong = process(matrix, arrived, next);
            }
            // 更新最大值
            if (pathLong > maxLong) {
                maxLong = pathLong;
            }
        }
        // 当前位置的路径最大长度为四周可走位置的路径的最大值+自己这个位置（1）
        arrived[curX][curY] = maxLong + 1;
        return maxLong + 1;
    }
}