Cat and Mouse
Hard · Graphs · Math · Dynamic Programming · Graph · Topological Sort · Memoization · Game Theory
Problem
A mouse and a cat play a game on an undirected graph given as graph, where graph[a] lists the nodes adjacent to a. The mouse starts at node 1 and moves first, the cat starts at node 2, and there is a hole at node 0.
The players alternate, and on each turn the player must move along an edge to an adjacent node. The cat may never enter node 0.
The game ends as soon as one of these happens:
- the cat lands on the mouse's node: the cat wins;
- the mouse reaches node 0: the mouse wins;
- a position (mouse node, cat node, player to move) repeats: it is a draw.
Both play optimally. Return 1 if the mouse wins, 2 if the cat wins, or 0 for a draw.
Examples
Input: graph = [[1,3],[0],[3],[0,2]] Output: 1
Node 1 touches the hole, so the mouse escapes on its first move.
Input: graph = [[2],[2],[0,1]] Output: 2
The mouse's only move is onto node 2, where the cat is waiting.
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0
Neither side can force a result: the mouse cannot get past the cat to the hole, and the cat cannot corner the mouse, so with best play positions repeat.
Constraints
- 3 <= len(graph) <= 50
- 1 <= len(graph[i]) < len(graph)
- 0 <= graph[i][j] < len(graph)
- graph[i][j] != i and graph[i] has no duplicates; the graph is undirected
- Every node other than 0 has at least one neighbor other than 0, so both players can always move
Approaches
- Sweep all positions until nothing changes — time O(n⁵) worst case, space O(n²)
Follow-up
What if a game lasting more than a fixed number of moves counted as a draw? Then a position needs the number of moves left as part of the state, and a plain bottom-up DP over that counter replaces the backward search.
Related problems
Start free on Cariara · Coding problems · System design studio
