Sponsored
Sponsored
This approach uses dynamic programming with a 3D array to store the results for each game state. We use the state (mouse and cat positions, and the current turn) to determine the game's outcome. This helps us avoid redundant computations and efficiently reach a solution through recursive calls. Each possible state is evaluated based on whether the mouse or cat can win from that point, or if it's a draw.
Time Complexity: O(N^3), where N is the number of graph nodes, since we try each node for mouse, cat, and turns.
Space Complexity: O(N^2), owing to storage in the DP table.
1def catMouseGame(graph):
2 N = len(graph)
3 DRAW, MOUSE, CAT = 0, 1, 2
4 state = [[[DRAW] * N for _ in range(N)] for _ in range(2 * N)]
5
6 for i in range(N):
7 for t in range(2 * N):
8 state[t][i][i] = CAT
9 state[t][0][i] = MOUSE
10
11 def can_mouse_win(t, mouse, cat):
12 if t == 2 * N or state[t][mouse][cat] != DRAW:
13 return state[t][mouse][cat]
14
15 if t % 2 == 0:
16 result = CAT
17 for next_mouse in graph[mouse]:
18 if next_mouse == cat:
19 continue
20 if can_mouse_win(t + 1, next_mouse, cat) == MOUSE:
21 result = MOUSE
22 break
23 elif can_mouse_win(t + 1, next_mouse, cat) == DRAW:
24 result = DRAW
25 state[t][mouse][cat] = result
26 else:
27 result = MOUSE
28 for next_cat in graph[cat]:
29 if next_cat == 0:
30 continue
31 if can_mouse_win(t + 1, mouse, next_cat) == CAT:
32 result = CAT
33 break
34 elif can_mouse_win(t + 1, mouse, next_cat) == DRAW:
35 result = DRAW
36 state[t][mouse][cat] = result
37
38 return state[t][mouse][cat]
39
40 return can_mouse_win(0, 1, 2)This approach uses a breadth-first search (BFS) combined with memoization to handle game states. We use a queue to systematically explore potential moves for both the mouse and cat, updating states based on the outcomes of previous states. This approach effectively captures the transitions and dependencies among various game states, systematically moving towards an outcome.
Time Complexity: O(N^3), as each state must be iterated for mouse, cat and move number combinations.
Space Complexity: O(N^2), due to storing states in the DP table with a queue usage.
1from collections import deque
2
3def catMouseGame(graph):
4
This approach is based on a recursive minimax algorithm with memoization to optimize overlapping subproblems. We represent the game state as a triplet (mouse_position, cat_position, turn), and use memoization to store results of states that have been computed before.
Each state evaluates its possible next states recursively, calculating whether it's a guaranteed win, loss, or draw from that position.
Time Complexity: O(n^3) - In the worst case, each state (mouse position, cat position, turn) is visited once for every player due to memoization.
Space Complexity: O(n^2) - Space used by the memoization cache, capturing every unique state evaluated.
1from functools import lru_cache
2
3
This approach uses a breadth-first search (BFS) method in which we 'color' the nodes based on current positions and outcomes as we traverse the graph. This approach focuses on evaluating the nodes with terminal states quickly and propagating results efficiently to neighbors. The 'coloring' means marking nodes with direct results like wins or losses and progressively marking draws as paths are evaluated.
Time Complexity: O(n^3) - BFS explores states by all node combinations leading to exhaustive evaluations, ensuring each is processed to fixed evaluation.
Space Complexity: O(n^2) - Each node stores multiple state outcomes efficiently within a moderate space allocation.
1var catMouseGame = function(graph)
This Python solution uses a recursive function with memoization (via lru_cache) to decide the outcome at each state. The base states evaluate whether the mouse wins (reaches 0), the cat wins (occupies the same node as the mouse), or if the number of turns suggests a draw. Depending on whether it's the mouse's or cat's turn, the function iterates over possible moves, recursively determining and memorizing possible outcomes. The solution makes use of depth-first exploration to optimize using previously computed states.
In this JavaScript solution, a color array tracks the win/draw state of every mouse, cat position at both even and odd turns. outDegree tracks remaining unexplored branch counts for optimization, simplifying the process of detecting draws. This BFS-based solution suits JavaScript well due to the languageās strength in managing asynchronous operations through event loops, thus efficiently simulating game states without recursion depth concerns.