import java.util.*;

/**
 * 解题思路: (深度优先遍历 + 动态规划)
 * 这是一道很难,很综合类的题目,认真做完后真的会收获很多
 * 首先一上来,我们肯定能想到用深度优先算法进行寻找最长递增路径,但是我们无法确定那个元素作为起点的时候,
 * 最长递增路径最长,因此我们只能每个元素都作为起点,求出其最长递增路径的长度,之后选取最长的即可.这样子
 * 想之后,毫无疑问时间复杂度很高很高,因此我们必须想办法进行优化.同时还有一个问题就是我们在进行深度优先
 * 遍历的时候,是否会出现走回路的情况(这个必须想清楚).
 * 首先我们考虑第二个回路的问题: 本题要求很好的避免了走回路的问题,我们不需要一个单独的矩阵来记录遍历过
 * 的元素了,因为题目中要求的是递增的路径,因此我们 dfs 中每从一个元素进入下一个元素,则下一个元素一定比
 * 当前元素大,且比其之前的每一个元素都大,因此不可能出现回路的情况.
 * 其次考虑第一个时间复杂度的问题: 我们认真思考我们的 dfs 过程,其实我们每次递归进入一个新的元素,都要
 * 求出以这个元素为起点的最长递增路径,且在我们求出以每个点作为起点的最长递归路径的时候,肯定会重复求以一
 * 些元素作为起点的最长递增路径,因此我们就想利用一个 dp 矩阵,对应每一次递归过程中,如果求出了以某个元素
 * 作为起点的最长递增路径时,就直接填入dp数组中,且在我们的 dfs 中,递归到(row,col)元素的时候,
 * 若dp[row][col] != 0 ,即表示以该元素作为起点的最长递增路径我们已经求出来了,直接选用即可,不再继续
 * dfs 下去,极大的减少了时间复杂度,这是典型的空间换取时间的做法.
 *
 * 本题答案中还有一个很巧妙的东西,就是实现向上下左右移动的时候,使用了一个 direction 数组来记录上下左右
 * 四个方向,在 dfs 过程中直接使用循环来实现向上下左右移动,避免书写重复的代码,真的很巧妙!!
 */
public class Solution {
    private static final int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
    public int solve (int[][] matrix) {
        //判空处理
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        //记录以 matrix[i][j] 为起点的最长递归路径的长度
        int[][] dp = new int[matrix.length][matrix[0].length];
        //记录最长递归路径的长度
        int maxLen = 0;
        //求出以每个点作为起点的最长递归路径
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (dp[i][j] == 0) {
                    dp[i][j] = dfs(matrix,dp,i,j);
                }
                maxLen = Math.max(maxLen,dp[i][j]);
            }
        }
        return maxLen;
    }

    /**
     * 深度优先搜索最长递增路径
     * @param matrix   记录原数字的矩阵
     * @param dp       记录以 matrix[i][j] 为起点的最长递归路径的长度的矩阵
     * @param row      当前行
     * @param col      当前列
     * @return
     */
    private static int dfs(int[][] matrix, int[][] dp, int row, int col) {
        //原先的递归遍历中已经求出过以该点为起点的最长递归路径的长度,直接用即可
        if (dp[row][col] != 0) {
            return dp[row][col];
        }
        int maxLen = 0;
        //遍历四个方向
        for (int k = 0; k < 4; k++) {
            int i = row + direction[k][0];
            int j = col + direction[k][1];
            if (i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length && matrix[i][j] > matrix[row][col]) {
                maxLen = Math.max(maxLen,dfs(matrix,dp,i,j));
            }
        }
        //别忘了当前元素也为路径中的一员
        maxLen++;
        //维护 dp 数组
        dp[row][col] = maxLen;
        return maxLen;
    }
}