Cat and Mouse LeetCode solution in Java

1
class Solution {
2
  int TIME_MAX = 200;
3
  int DRAW = 0;
4
  int MOUSE_WIN = 1;
5
  int CAT_WIN = 2;
6

7
  public int catMouseGame(int[][] graph) {
8
    return dfs(0, new int[] {1, 2}, graph, new Integer[TIME_MAX + 1][graph.length][graph.length]);
9
  }
10

11
  private int dfs(
12
      int time,
13
      int[] p,
14
      int[][] graph,
15
      Integer[][][] memo) { // p[0] -> mouse position, p[1] -> cat position
16
    Integer old = memo[time][p[0]][p[1]];
17
    if (old != null) return old; // all the base cases here
18
    if (time >= TIME_MAX) return DRAW;
19
    if (p[0] == 0) return MOUSE_WIN;
20
    if (p[0] == p[1]) return CAT_WIN;
21
    int state = 0;
22
    int where = p[time & 1];
23
    int res = DRAW;
24
    for (int i = 0; i < graph[where].length; i++) {
25
      if ((time & 1) == 0
26
          || graph[where][i] > 0) { // if mouse turn or cat turn and the dest is not 0, do ...
27
        p[time & 1] = graph[where][i];
28
        state |= 1 << dfs(time + 1, p, graph, memo);
29
        if ((time & 1) > 0 && (state & 4) > 0
30
            || (time & 1) == 0 && (state & 2) > 0) // if mouse's turn & mouse win
31
        break; // or cat's turn & cat win, then we stop.
32
      }
33
    }
34
    p[time & 1] = where; // restore p
35
    if (((time & 1) > 0 && (state & 4) > 0) || ((time & 1) == 0) && state == 4) {
36
      res = CAT_WIN; // cat win when (cat's turn & cat win) or (mouse's turn and state = cat)
37
    } else if (((time & 1) == 0 && (state & 2) > 0) || (time & 1) == 1 && state == 2) {
38
      res = MOUSE_WIN; // mouse win when (mouse's turn and mouse win) or (cat's turn and state =
39
      // mouse)
40
    }
41
    return memo[time][p[0]][p[1]] = res;
42
  }
43
}