Skip to content

913. Cat and Mouse 👍

  • Time: $O(n^3)$
  • Space: $O(n^3)$
 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
47
48
49
50
51
52
53
54
55
56
57
58
enum class State { kDraw, kMouseWin, kCatWin };

class Solution {
 public:
  int catMouseGame(vector<vector<int>>& graph) {
    const int n = graph.size();
    // result of (cat, mouse, move)
    // move := 0 (mouse) / 1 (cat)
    vector<vector<vector<State>>> states(
        n, vector<vector<State>>(n, vector<State>(2)));
    vector<vector<vector<int>>> outDegree(
        n, vector<vector<int>>(n, vector<int>(2)));
    queue<tuple<int, int, int, State>> q;  // (cat, mouse, move, state)

    for (int cat = 0; cat < n; ++cat)
      for (int mouse = 0; mouse < n; ++mouse) {
        outDegree[cat][mouse][0] = graph[mouse].size();
        outDegree[cat][mouse][1] =
            graph[cat].size() - ranges::count(graph[cat], 0);
      }

    // Start from the states s.t. the winner can be determined.
    for (int cat = 1; cat < n; ++cat)
      for (int move = 0; move < 2; ++move) {
        // Mouse is in the hole.
        states[cat][0][move] = State::kMouseWin;
        q.emplace(cat, 0, move, State::kMouseWin);
        // Cat catches mouse.
        states[cat][cat][move] = State::kCatWin;
        q.emplace(cat, cat, move, State::kCatWin);
      }

    while (!q.empty()) {
      const auto [cat, mouse, move, state] = q.front();
      q.pop();
      if (cat == 2 && mouse == 1 && move == 0)
        return static_cast<int>(state);
      const int prevMove = move ^ 1;
      for (const int prev : graph[prevMove ? cat : mouse]) {
        const int prevCat = prevMove ? prev : cat;
        if (prevCat == 0)  // invalid
          continue;
        const int prevMouse = prevMove ? mouse : prev;
        // The state has been determined.
        if (states[prevCat][prevMouse][prevMove] != State::kDraw)
          continue;
        if (prevMove == 0 && state == State::kMouseWin ||
            prevMove == 1 && state == State::kCatWin ||
            --outDegree[prevCat][prevMouse][prevMove] == 0) {
          states[prevCat][prevMouse][prevMove] = state;
          q.emplace(prevCat, prevMouse, prevMove, state);
        }
      }
    }

    return static_cast<int>(states[2][1][0]);
  }
};

 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
47
48
49
50
51
52
53
54
55
56
57
enum State { kDraw, kMouseWin, kCatWin }

class Solution {
  public int catMouseGame(int[][] graph) {
    final int n = graph.length;
    // result of (cat, mouse, move)
    // move := 0 (mouse) / 1 (cat)
    int[][][] states = new int[n][n][2];
    int[][][] outDegree = new int[n][n][2];
    Queue<int[]> q = new ArrayDeque<>();

    for (int cat = 0; cat < n; ++cat)
      for (int mouse = 0; mouse < n; ++mouse) {
        outDegree[cat][mouse][0] = graph[mouse].length;
        outDegree[cat][mouse][1] =
            graph[cat].length - (Arrays.stream(graph[cat]).anyMatch(v -> v == 0) ? 1 : 0);
      }

    // Start from the states s.t. the winner can be determined.
    for (int cat = 1; cat < n; ++cat)
      for (int move = 0; move < 2; ++move) {
        // Mouse is in the hole.
        states[cat][0][move] = State.kMouseWin.ordinal();
        q.offer(new int[] {cat, 0, move, State.kMouseWin.ordinal()});
        // Cat catches mouse.
        states[cat][cat][move] = State.kCatWin.ordinal();
        q.offer(new int[] {cat, cat, move, State.kCatWin.ordinal()});
      }

    while (!q.isEmpty()) {
      final int cat = q.peek()[0];
      final int mouse = q.peek()[1];
      final int move = q.peek()[2];
      final int state = q.poll()[3];
      if (cat == 2 && mouse == 1 && move == 0)
        return state;
      final int prevMove = move ^ 1;
      for (final int prev : graph[prevMove == 0 ? mouse : cat]) {
        final int prevCat = prevMove == 0 ? cat : prev;
        if (prevCat == 0) // invalid
          continue;
        final int prevMouse = prevMove == 0 ? prev : mouse;
        // The state has been determined.
        if (states[prevCat][prevMouse][prevMove] > 0)
          continue;
        if (prevMove == 0 && state == State.kMouseWin.ordinal() ||
            prevMove == 1 && state == State.kCatWin.ordinal() ||
            --outDegree[prevCat][prevMouse][prevMove] == 0) {
          states[prevCat][prevMouse][prevMove] = state;
          q.offer(new int[] {prevCat, prevMouse, prevMove, state});
        }
      }
    }

    return states[2][1][0];
  }
}

 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
47
48
49
50
51
52
53
54
55
56
57
from enum import IntEnum


class State(IntEnum):
  kDraw = 0
  kMouseWin = 1
  kCatWin = 2


class Solution:
  def catMouseGame(self, graph: list[list[int]]) -> int:
    n = len(graph)
    # result of (cat, mouse, move)
    # move := 0 (mouse) // 1 (cat)
    states = [[[0] * 2 for i in range(n)] for j in range(n)]
    outDegree = [[[0] * 2 for i in range(n)] for j in range(n)]
    q = collections.deque()  # (cat, mouse, move, state)

    for cat in range(n):
      for mouse in range(n):
        outDegree[cat][mouse][0] = len(graph[mouse])
        outDegree[cat][mouse][1] = len(graph[cat]) - graph[cat].count(0)

    # Start from the states s.t. the winner can be determined.
    for cat in range(1, n):
      for move in range(2):
        # Mouse is in the hole.
        states[cat][0][move] = int(State.kMouseWin)
        q.append((cat, 0, move, int(State.kMouseWin)))
        # Cat catches mouse.
        states[cat][cat][move] = int(State.kCatWin)
        q.append((cat, cat, move, int(State.kCatWin)))

    while q:
      cat, mouse, move, state = q.popleft()
      if cat == 2 and mouse == 1 and move == 0:
        return state
      prevMove = move ^ 1
      for prev in graph[cat if prevMove else mouse]:
        prevCat = prev if prevMove else cat
        if prevCat == 0:  # invalid
          continue
        prevMouse = mouse if prevMove else prev
        # The state has been determined.
        if states[prevCat][prevMouse][prevMove]:
          continue
        if (prevMove == 0 and state == int(State.kMouseWin) or
                prevMove == 1 and state == int(State.kCatWin)):
          states[prevCat][prevMouse][prevMove] = state
          q.append((prevCat, prevMouse, prevMove, state))
        else:
          outDegree[prevCat][prevMouse][prevMove] -= 1
          if outDegree[prevCat][prevMouse][prevMove] == 0:
            states[prevCat][prevMouse][prevMove] = state
            q.append((prevCat, prevMouse, prevMove, state))

    return states[2][1][0]