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

import java.util.*;


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

    int max = 0;
    boolean[][] visited;

    public int solve (int[][] matrix) {
        // write code here
        visited = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i ++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dfs(matrix, i, j, 0, Integer.MIN_VALUE);
            }
        }

        return max;
    }

    private void dfs (int[][] matrix, int x, int y, int dis, int pre) {

        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) { // 越界即停
            if (max < dis) { // 结算，直至走到上一个坐标，路径长度dis是否比max还要大
                max = dis;
            }
            return;
        }

        if (!visited[x][y] && pre < matrix[x][y]) { // 如果满足比上一个坐标点还要大，就证明该点是合法点，可以继续往下走
            visited[x][y] = true;
            dfs(matrix, x - 1, y, dis + 1, matrix[x][y]); //上
            dfs(matrix, x + 1, y, dis + 1, matrix[x][y]); //下
            dfs(matrix, x, y - 1, dis + 1, matrix[x][y]); //左
            dfs(matrix, x, y + 1, dis + 1, matrix[x][y]); //右
            visited[x][y] = false;
        } else { 
            // 如果不满足上述条件，证明自己走到了不该走（不合法）的地方，这时候马上结算，
            // 直至走到上一个坐标，路径长度dis是否比max还要大
            if (max < dis) {
                max = dis;
            }
        }
    }
}