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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
 */
function solve(matrix) {
    // write code here
    let n = matrix.length;
    if (n == 0) {
        return 0;
    }
    let m = matrix[0].length;
    let p = [];
    for (let i = 0; i < n; i++) {
        p.push([]);
        for (let j = 0; j < m; ++j) {
            p[i].push(0);
        }
    }
    let xx = [-1, 1, 0, 0], yy = [0, 0, 1, -1];
    function dfs(x, y) {
        for (let i = 0; i < 4; ++i) {
            let nx = x + xx[i], ny = y + yy[i];
            // 检查边界和是否递增
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] > matrix[x][y]) {
                let dp = dfs(nx, ny) + 1;
                p[x][y] = dp > p[x][y] ? dp : p[x][y];
            }
        }
        return p[x][y];
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; ++j) {
            let dp = dfs(i, j) + 1;
            ans = ans > dp ? ans : dp;
        }
    }
    return ans;
}
module.exports = {
    solve: solve
};