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

矩阵最长递增路径

https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
     int count = 0;
    public int solve (int[][] matrix) {
        // write code here
        for (int i = 0; i < matrix.length; i++) {
            for (int t = 0; t < matrix[0].length; t++) {
                dfs(matrix, 1, i, t);
            }
        }
        return count;
    }

    public void dfs(int[][] matrix, int depth, int n, int m) {
        int temp = matrix[n][m];
        //System.out.print("" + n + ":" + m +"||"+temp + "  ");
        if (!((n-1 >= 0 && matrix[n-1][m] > temp) || (m-1 >= 0 && matrix[n][m-1] > temp) || 
        (n+1 < matrix.length && matrix[n+1][m] > temp) || (m+1 < matrix[0].length && matrix[n][m+1] > temp))) {
            //System.out.print(" " + matrix[1][0] + " bingo ");
            if (count < depth) count = depth;
            return;
        }
        //上
        if (n-1 >= 0 && matrix[n-1][m] > temp) {
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n-1,m);
            matrix[n][m] = temp;
        }
        //左
        if (m-1 >= 0 && matrix[n][m-1] > temp) {
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n,m-1);
            matrix[n][m] = temp;
        }
        //下
        if (n+1 < matrix.length && matrix[n+1][m] > temp) {
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n+1,m);
            matrix[n][m] = temp;
        }
        //右
        if (m+1 < matrix[0].length && matrix[n][m+1] > temp){
            matrix[n][m] = -1;
            dfs(matrix,depth+1,n,m+1);
            matrix[n][m] = temp;
        }
    }
}

全部评论

相关推荐

11-11 14:21
西京学院 C++
无敌混子大王:首先一点,不管学校层次怎么样,教育经历放在第一页靠上位置,第一页看不到教育经历,hr基本直接扔掉了
点赞 评论 收藏
分享
头像
11-21 11:39
四川大学 Java
是红鸢啊:忘了还没结束,还有字节的5k 违约金
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务