# 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>& graph) { const int n = graph.size(); // Result of (cat, mouse, move) // Move := 0 (mouse) / 1 (cat) vector>> states( n, vector>(n, vector(2))); vector>> outDegree( n, vector>(n, vector(2))); queue> q; // (cat, mouse, move, state) for (int cat = 0; cat < n; ++cat) for (int mouse = 0; mouse < n; ++mouse) { outDegree[cat][mouse] = graph[mouse].size(); outDegree[cat][mouse] = graph[cat].size() - count(begin(graph[cat]), end(graph[cat]), 0); } // Start from states that winner can be determined for (int cat = 1; cat < n; ++cat) for (int move = 0; move < 2; ++move) { // Mouse is in the hole -> State::kMouseWin states[cat][move] = State::kMouseWin; q.emplace(cat, 0, move, State::kMouseWin); // Cat catches mouse -> State::kCatWin 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(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 is already 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(states); } }; 
  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]; int[][][] outDegree = new int[n][n]; Queue q = new ArrayDeque<>(); for (int cat = 0; cat < n; ++cat) for (int mouse = 0; mouse < n; ++mouse) { outDegree[cat][mouse] = graph[mouse].length; outDegree[cat][mouse] = graph[cat].length - (Arrays.stream(graph[cat]).anyMatch(v -> v == 0) ? 1 : 0); } // Start from states that winner can be determined for (int cat = 1; cat < n; ++cat) for (int move = 0; move < 2; ++move) { // Mouse is in the hole -> MOUSE WIN states[cat][move] = State.kMouseWin.ordinal(); q.offer(new int[] {cat, 0, move, State.kMouseWin.ordinal()}); // Cat catches mouse -> kCatWin 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(); final int mouse = q.peek(); final int move = q.peek(); final int state = q.poll(); 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 is already 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; } } 
  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 = [[ * 2 for i in range(n)] for j in range(n)] outDegree = [[ * 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] = len(graph[mouse]) outDegree[cat][mouse] = len(graph[cat]) - graph[cat].count(0) # Start from states that winner can be determined for cat in range(1, n): for move in range(2): # Mouse is in the hole . kMouseWin states[cat][move] = int(State.kMouseWin) q.append((cat, 0, move, int(State.kMouseWin))) # Cat catches mouse . kCatWin 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 is already 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