Longest Increasing Path in a Matrix LeetCode solution in Rust

1
impl Solution {
2
  pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
3
    let (m, n) = (matrix.len(), matrix[0].len());
4
    let mut cache = vec![vec![None; n]; m];
5
    let mut answer = 0;
6
    for i in 0..m {
7
      for j in 0..n {
8
        answer = answer.max(Self::dfs(&matrix, &mut cache, i, j));
9
      }
10
    }
11
    answer
12
  }
13
  fn dfs(matrix: &[Vec<i32>], cache: &mut Vec<Vec<Option<i32>>>, i: usize, j: usize) -> i32 {
14
    if let Some(c) = cache[i][j] {
15
      return c;
16
    }
17
    let (m, n) = (matrix.len(), matrix[0].len());
18
    let mut ret = 1;
19
    for d in [0, -1, 0, 1, 0].windows(2) {
20
      let (ni, nj) = (i as i32 + d[0], j as i32 + d[1]);
21
      if (0..m as i32).contains(&ni) && (0..n as i32).contains(&nj) {
22
        let (ni, nj) = (ni as usize, nj as usize);
23
        if matrix[ni][nj] > matrix[i][j] {
24
          ret = ret.max(Self::dfs(matrix, cache, ni, nj) + 1);
25
        }
26
      }
27
    }
28
    cache[i][j] = Some(ret);
29
    ret
30
  }
31
}