题解 | #矩阵最长递增路径#通俗易懂

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    
    int max;
    boolean[][] used;
    
    public int solve (int[][] matrix) {
        if(matrix == null || matrix.length == 0) {
            return 0;
        }
       
        used = 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,-1);
              //从所有点dfs
            }
        }
        return max;
    }

    private void dfs(int[][] matrix, int i, int j,int count,int n) {
        if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
          //走到边界外了 直接返回  
          return;
        }
        if(matrix[i][j] <= n || used[i][j]) {
          //走到小于上一个的了  直接返回  ||  走到走过的地方了
          //保存递增路径的长度  因为走到这里意味着这个路径已经走完了 已经是该路径下最长的长度了
            max = Math.max(max,count);
            return;
        }
      	//走当前的位置 标记走过了
        used[i][j] = true;
      	//记录当前这一步的值  为下一步的值提供对照 避免走到小于或者等于的值
        n = matrix[i][j];
      	//上下左右的走 
        dfs(matrix,i+1,j,count+1,n);
        dfs(matrix,i-1,j,count+1,n);
        dfs(matrix,i,j+1,count+1,n);
        dfs(matrix,i,j-1,count+1,n);
        used[i][j] = false;
      	//往上一步递归回退时 取消当前这一步走的影响 这里n会因为局部变量栈帧销毁 所以还是原来的值
    }
}