1
2
3

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。

1
2
3

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

1
2

输入：matrix = [[1]]
输出：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - dfs
    pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
        //
        fn dfs(matrix: &[Vec<i32>], step: (usize, usize), stat: &mut Vec<Vec<Option<i32>>>) -> i32 {
            // 如果该点遍历过, 则直接返回;
            if let Some(c) = stat[step.0][step.1] {
                return c;
            }
            let mut ret = 1;
            // 从该点开始, 前后左右四个方向递归遍历
            for d in [0, -1, 0, 1, 0].windows(2) {
                let (ni, nj) = ((step.0 as i32) + d[0], (step.1 as i32) + d[1]);
                let (ni, nj) = (ni as usize, nj as usize);
                if (0..matrix.len()).contains(&ni) && (0..matrix[0].len()).contains(&nj) {
                    // 递增方向
                    if matrix[ni][nj] > matrix[step.0][step.1] {
                        // 当前坐标路径最大递增长度 为四个方向中最长的那个+1
                        ret = ret.max(dfs(matrix, (ni, nj), stat) + 1);
                    }
                }
            }
            // 记录该坐标最长递增路径
            stat[step.0][step.1] = Some(ret);

            ret
        }

        let mut res = 0;
        let mut stat = vec![vec![None; matrix[0].len()]; matrix.len()];
        for i in 0..matrix.len() {
            for j in 0..matrix[0].len() {
                // 所有点开始的最长递增路径 中 最大的
                res = res.max(dfs(&matrix, (i, j), &mut stat));
            }
        }

        res
    }
}
// @lc code=end

struct Solution;