题解 | #矩阵最长递增路径#
矩阵最长递增路径
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; } } }