A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.
The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.
The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0.
During each player's turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].
Additionally, it is not allowed for the Cat to travel to the Hole (node 0).
Then, the game can end in three ways:
Given a graph, and assuming both players play optimally, return
1 if the mouse wins the game,2 if the cat wins the game, or0 if the game is a draw.
Example 1:
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0
Example 2:
Input: graph = [[1,3],[0],[3],[0,2]] Output: 1
Constraints:
3 <= graph.length <= 501 <= graph[i].length < graph.length0 <= graph[i][j] < graph.lengthgraph[i][j] != igraph[i] is unique.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.
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.
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.
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.
Java
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.
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.
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.
C#
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.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | 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. |
| Breadth-First Search with Memoization | 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. |
| Approach 1: Minimax with Memoization | 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. |
| Approach 2: BFS with Coloring Method | 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. |
Game of Cat and Mouse - Numberphile • Numberphile • 1,467,885 views views
Watch 9 more video solutions →Practice Cat and Mouse with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor