Cat and Mouse II LeetCode solution in Java

1
class Solution {
2
  int[] dx = new int[] {0, 0, 1, -1};
3
  int[] dy = new int[] {-1, 1, 0, 0};
4
  int m;
5
  int n;
6
  int TIME_MAX = 100;
7

8
  public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
9
    m = grid.length;
10
    n = grid[0].length();
11
    int mouseI = 0, mouseJ = 0;
12
    int catI = 0, catJ = 0;
13
    for (int i = 0; i < m; i++) {
14
      for (int j = 0; j < n; j++) {
15
        switch (grid[i].charAt(j)) {
16
          case 'M' -> {
17
            mouseI = i;
18
            mouseJ = j;
19
          }
20
          case 'C' -> {
21
            catI = i;
22
            catJ = j;
23
          }
24
        }
25
      }
26
    }
27
    return dfs(
28
        0,
29
        mouseI,
30
        mouseJ,
31
        catI,
32
        catJ,
33
        catJump,
34
        mouseJump,
35
        grid,
36
        new Boolean[TIME_MAX + 1][m][n][m][n]);
37
  }
38

39
  private boolean dfs(
40
      int time,
41
      int mI,
42
      int mJ,
43
      int cI,
44
      int cJ,
45
      int cJump,
46
      int mJump,
47
      String[] grid,
48
      Boolean[][][][][] memo) {
49
    if (grid[mI].charAt(mJ) == 'F') { // mouse got the food -> mouse won
50
      return true;
51
    }
52
    if (grid[cI].charAt(cJ) == 'F' || cI == mI && cJ == mJ || time > TIME_MAX) {
53
      return false; // cat got the food / draw / cat got the mouse -> cat won.
54
    }
55
    if (memo[time][mI][mJ][cI][cJ] != null) {
56
      return memo[time][mI][mJ][cI][cJ];
57
    }
58
    boolean mT = time % 2 == 0;
59
    int jump = mT ? mJump : cJump;
60
    int x = mT ? mI : cI;
61
    int y = mT ? mJ : cJ;
62
    if (!mT && !dfs(time + 1, mI, mJ, cI, cJ, cJump, mJump, grid, memo)) {
63
      return memo[time][mI][mJ][cI][cJ] = false; // cat's turn and cat stays still and cat won
64
    }
65
    for (int i = 0; i < 4; i++) {
66
      for (int j = 1; j <= jump; j++) {
67
        int nx = x + dx[i] * j;
68
        int ny = y + dy[i] * j;
69
        if (nx < 0 || ny < 0 || nx == m || ny == n || grid[nx].charAt(ny) == '#') {
70
          break; // note that cat & mouse can't jump over #. I got a WA thinking they can jump over
71
          // it.
72
        }
73
        boolean res =
74
            dfs(
75
                time + 1,
76
                mT ? nx : mI,
77
                mT ? ny : mJ,
78
                mT ? cI : nx,
79
                mT ? cJ : ny,
80
                cJump,
81
                mJump,
82
                grid,
83
                memo);
84
        if (mT && res) { // if it is mouse's turn and it can find ONE way to win, then mouse win.
85
          return memo[time][mI][mJ][cI][cJ] = true;
86
        }
87
        if (!mT
88
            && !res) { // if it is cat's turn and it can find ONE way to a draw or cat win, then cat
89
          // win
90
          return memo[time][mI][mJ][cI][cJ] = false;
91
        }
92
      }
93
    }
94
    return memo[time][mI][mJ][cI][cJ] = !mT; // otherwise, return !mT
95
  }
96
}