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

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

// 向四个方向分别探索，深度优先算法

function dfs(matrix, i, j) {
    let x = matrix.length;
    let y = matrix[0].length;
    let cur = matrix[i][j];
    // let res = [];
    let max = 1;
    if (i - 1 >= 0) {
        let left = matrix[i - 1][j];
        if (cur < left) {
            left = dfs(matrix, i - 1, j) + 1;
            if (Number.isNaN(left)) {
                console.log(i, j);
            }
            max = Math.max(max,  left);
        }
    }
    if (i + 1 <= x - 1) {
        let right = matrix[i + 1][j];
        if (cur < right) {
            right = dfs(matrix, i + 1, j) + 1;
            if (Number.isNaN(right)) {
                console.log(i, j);
            }
            max = Math.max(max,  right);
        }
    }
    if (j - 1 >= 0) {
        let up = matrix[i][j - 1];
        if (cur < up) {
            up = dfs(matrix, i, j - 1) + 1;
            if (Number.isNaN(up)) {
                console.log(i, j);
            }
            max = Math.max(max,  up);
        }
    }
    if (j + 1 <= y - 1) {
        let down = matrix[i][j + 1];
        if (cur < down) {
            down = dfs(matrix, i, j + 1) + 1;
            if (Number.isNaN(down)) {
                console.log(i, j);
            }
            max = Math.max(max,  down);
        }
    }

    return max;
}

function solve(matrix) {
    // write code here
    let x = matrix.length;
    let y = matrix[0].length;
    // 对每一个节点进行深度优先计算，求出在该节点下的最长距离push进res数组中
    let res = [];
    for (let i = 0; i < x; i++) {
        for (let j = 0; j < y; j++) {
            res.push(dfs(matrix, i, j));
        }
    }
    return Math.max(...res);
}
module.exports = {
    solve: solve,
};