# 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 { DRAW, MOUSE_WIN, CAT_WIN }; 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::MOUSE_WIN states[cat][move] = State::MOUSE_WIN; q.emplace(cat, 0, move, State::MOUSE_WIN); // cat catches mouse -> State::CAT_WIN states[cat][cat][move] = State::CAT_WIN; q.emplace(cat, cat, move, State::CAT_WIN); } 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::DRAW) continue; if (prevMove == 0 && state == State::MOUSE_WIN || prevMove == 1 && state == State::CAT_WIN || --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 { DRAW, MOUSE_WIN, CAT_WIN } 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.MOUSE_WIN.ordinal(); q.offer(new int[] {cat, 0, move, State.MOUSE_WIN.ordinal()}); // cat catches mouse -> CAT_WIN states[cat][cat][move] = State.CAT_WIN.ordinal(); q.offer(new int[] {cat, cat, move, State.CAT_WIN.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.MOUSE_WIN.ordinal() || prevMove == 1 && state == State.CAT_WIN.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): DRAW = 0 MOUSE_WIN = 1 CAT_WIN = 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 = 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 . MOUSE_WIN states[cat][move] = int(State.MOUSE_WIN) q.append((cat, 0, move, int(State.MOUSE_WIN))) # cat catches mouse . CAT_WIN states[cat][cat][move] = int(State.CAT_WIN) q.append((cat, cat, move, int(State.CAT_WIN))) 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.MOUSE_WIN) or \ prevMove == 1 and state == int(State.CAT_WIN): 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