Cat and Mouse II LeetCode solution in Rust

1
impl Solution {
2
  pub fn can_mouse_win(grid: Vec<String>, cat_jump: i32, mouse_jump: i32) -> bool {
3
    fn get_jumps(grid: &Vec<String>, p: i32, f: i32, max: i32) -> Vec<i32> {
4
      let dirs = [0, 1, 0, -1, 0];
5
      let mut res = vec![p];
6
      for d in 0..4 {
7
        for jump in 1..=max {
8
          let i = p / 8 + dirs[d] * jump;
9
          let j = p % 8 + dirs[d + 1] * jump;
10
          if i < 0
11
            || j < 0
12
            || i as usize >= grid.len()
13
            || j as usize >= grid[i as usize].len()
14
            || grid[i as usize].chars().nth(j as usize).unwrap() == '#'
15
          {
16
            break;
17
          }
18
          res.push(i * 8 + j);
19
        }
20
      }
21
      res.sort_by(|&a, &b| {
22
        let v1 = (f / 8 - a / 8).abs() + (f % 8 - a % 8).abs();
23
        let v2 = (f / 8 - b / 8).abs() + (f % 8 - b % 8).abs();
24
        v1.cmp(&v2)
25
      });
26
      res
27
    }
28

29
    #[allow(clippy::too_many_arguments)]
30
    fn dfs(
31
      grid: &Vec<String>,
32
      turn: i32,
33
      c: i32,
34
      m: i32,
35
      f: i32,
36
      cat_jump: i32,
37
      mouse_jump: i32,
38
      dp: &mut Vec<Vec<Vec<i32>>>,
39
    ) -> bool {
40
      if turn >= 0 && (m == f || dp[turn as usize][m as usize][c as usize] == 1) {
41
        return true;
42
      }
43
      if turn < 0 || c == m || c == f || dp[turn as usize][m as usize][c as usize] == -1 {
44
        return false;
45
      }
46
      let cat_jumps = get_jumps(grid, c, f, cat_jump);
47
      for new_m in get_jumps(grid, m, f, mouse_jump) {
48
        let mut mouse_won = true;
49
        for &jmp in cat_jumps.iter() {
50
          mouse_won &= dfs(grid, turn - 1, jmp, new_m, f, cat_jump, mouse_jump, dp);
51
        }
52
        if mouse_won {
53
          dp[turn as usize][m as usize][c as usize] = 1;
54
          return true;
55
        }
56
      }
57
      dp[turn as usize][m as usize][c as usize] = -1;
58
      false
59
    }
60

61
    let mut dp = vec![vec![vec![0; 64]; 64]; 64];
62
    let (mut c, mut m, mut f, rows, cols) =
63
      (0_i32, 0_i32, 0_i32, grid.len() as i32, grid[0].len() as i32);
64
    let turns = rows * cols - 1;
65
    for i in 0..rows {
66
      for j in 0..cols {
67
        m = if grid[i as usize].chars().nth(j as usize).unwrap() == 'M' {
68
          i * 8 + j
69
        } else {
70
          m
71
        };
72
        c = if grid[i as usize].chars().nth(j as usize).unwrap() == 'C' {
73
          i * 8 + j
74
        } else {
75
          c
76
        };
77
        f = if grid[i as usize].chars().nth(j as usize).unwrap() == 'F' {
78
          i * 8 + j
79
        } else {
80
          f
81
        };
82
      }
83
    }
84
    dfs(&grid, turns, c, m, f, cat_jump, mouse_jump, &mut dp)
85
  }
86
}