#913

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Cat and Mouse

Determine the outcome of a two-player Cat and Mouse game on a graph using topological ordering and memoized dynamic programming.

math dynamic programming graph topological sort memoization

Problem Statement

You are given an undirected graph representing a game played by two players: Mouse and Cat. The graph is given as an adjacency list graph, where graph[a] contains all nodes b such that there is an edge between nodes a and b. The Mouse starts at node 1, the Cat starts at node 2, and node 0 represents a hole where the Mouse can escape. The players alternate turns with the Mouse moving first.

The game ends if the Mouse reaches the hole, if the Cat catches the Mouse by moving to the same node, or if a position repeats causing a draw. Your task is to determine the result of the game: 1 if the Mouse can guarantee a win, 2 if the Cat can guarantee a win, and 0 if the game results in a draw, applying the graph indegree and topological ordering pattern to compute all reachable states efficiently.

Examples

Example 1

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]

Output: 0

Example details omitted.

Example 2

Input: graph = [[1,3],[0],[3],[0,2]]

Output: 1

Example details omitted.

Constraints

3 <= graph.length <= 50
1 <= graph[i].length < graph.length
0 <= graph[i][j] < graph.length
graph[i][j] != i
graph[i] is unique.
The mouse and the cat can always move.

Solution Approach

Model All Game States

Represent each combination of Mouse and Cat positions and the player's turn as a distinct state. Initialize winning states for the Mouse reaching node 0 and the Cat catching the Mouse. This state modeling directly maps to the graph indegree pattern used to track topological propagation.

Topological Sort via Indegree

Compute the outdegree of each state and use a queue to propagate results in reverse. When all subsequent moves of a state are winning for one player, mark the current state as losing for the other. This ensures cycles do not prevent correct outcome determination, reflecting the topological ordering method.

Dynamic Programming with Memoization

Memoize the result of each state to avoid recomputation. For each state, propagate the outcome to parent states until the initial configuration is resolved. This DP approach guarantees correctness and efficiency within the O(N^3) time and O(N^2) space bounds for graph length N.

Complexity Analysis

Metric	Value
Time	O(N^3)
Space	O(N^2)

The algorithm examines each combination of Mouse and Cat positions (O(N^2)) and each possible move from those positions (up to O(N)), yielding O(N^3) time complexity. Storing results for all states and turns requires O(N^2) space.

What Interviewers Usually Probe

Expect candidates to model states for both players explicitly using graph nodes and turns.
Look for correct handling of cycles and draw conditions using indegree-based propagation.
Verify memoization prevents repeated computation across overlapping subgames.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the Cat cannot move to node 0, breaking correct state transitions.
Not handling draw conditions when states repeat or indegree propagation stalls.
Incorrectly updating parent states before all child outcomes are resolved, leading to wrong results.

Follow-up variants

Change the starting positions of the Mouse and Cat to arbitrary nodes and analyze outcome.
Introduce multiple holes and adapt topological propagation to multiple winning terminal states.
Consider directed graphs where edges limit movement direction and recompute outcomes using the same DP pattern.

FAQ

What is the main pattern used in Cat and Mouse?

The core pattern is graph indegree plus topological ordering combined with memoized dynamic programming to resolve all game states.

Why do we need memoization in Cat and Mouse?

Memoization prevents recomputation of outcomes for repeated Mouse-Cat position pairs and turn sequences, ensuring efficiency and correctness.

How are draw conditions handled in this problem?

Draws occur when states repeat without reaching terminal conditions, and the algorithm marks such states after indegree propagation stalls.

Can this solution handle cycles in the graph?

Yes, the topological ordering with indegree tracking propagates results correctly even when cycles exist, preventing infinite loops.

What is the expected complexity for the Cat and Mouse solution?

The solution has O(N^3) time and O(N^2) space complexity due to iterating all Mouse-Cat position combinations and possible moves.

terminal

Solution

Solution 1: Topological Sorting

According to the problem description, the state of the game is determined by the position of the mouse, the position of the cat, and the player who is moving. The outcome can be directly determined in the following situations:

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

HOLE, MOUSE_START, CAT_START = 0, 1, 2
MOUSE_TURN, CAT_TURN = 0, 1
MOUSE_WIN, CAT_WIN, TIE = 1, 2, 0


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        def get_prev_states(state):
            m, c, t = state
            pt = t ^ 1
            pre = []
            if pt == CAT_TURN:
                for pc in graph[c]:
                    if pc != HOLE:
                        pre.append((m, pc, pt))
            else:
                for pm in graph[m]:
                    pre.append((pm, c, pt))
            return pre

        n = len(graph)
        ans = [[[0, 0] for _ in range(n)] for _ in range(n)]
        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(1, n):
                degree[i][j][MOUSE_TURN] = len(graph[i])
                degree[i][j][CAT_TURN] = len(graph[j])
            for j in graph[HOLE]:
                degree[i][j][CAT_TURN] -= 1
        q = deque()
        for j in range(1, n):
            ans[0][j][MOUSE_TURN] = ans[0][j][CAT_TURN] = MOUSE_WIN
            q.append((0, j, MOUSE_TURN))
            q.append((0, j, CAT_TURN))
        for i in range(1, n):
            ans[i][i][MOUSE_TURN] = ans[i][i][CAT_TURN] = CAT_WIN
            q.append((i, i, MOUSE_TURN))
            q.append((i, i, CAT_TURN))
        while q:
            state = q.popleft()
            t = ans[state[0]][state[1]][state[2]]
            for prev_state in get_prev_states(state):
                pm, pc, pt = prev_state
                if ans[pm][pc][pt] == TIE:
                    win = (t == MOUSE_WIN and pt == MOUSE_TURN) or (
                        t == CAT_WIN and pt == CAT_TURN
                    )
                    if win:
                        ans[pm][pc][pt] = t
                        q.append(prev_state)
                    else:
                        degree[pm][pc][pt] -= 1
                        if degree[pm][pc][pt] == 0:
                            ans[pm][pc][pt] = t
                            q.append(prev_state)
        return ans[MOUSE_START][CAT_START][MOUSE_TURN]

Continue Practicing

#1728 cat and mouse ii #464 can i win #329 longest increasing path in a matrix