LeetCode 913: Cat and Mouse

Problem Restatement

We are given an undirected graph.

Mouse starts at node 1.

Cat starts at node 2.

The hole is node 0.

Mouse moves first. Then Cat moves. They alternate turns.

On each turn, the current player must move along one graph edge. Cat is not allowed to move into node 0.

The game ends in one of three ways:

Return:

1  # mouse wins
2  # cat wins
0  # draw

Both players play optimally. The statement defines the graph, starting positions, hole rule, win rules, and draw rule this way.

Input and Output

Function shape:

def catMouseGame(graph: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

Answer:

0

The result is a draw with optimal play.

Example 2:

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

Answer:

1

Mouse can force a win.

First Thought: DFS With Memoization

A natural idea is to use recursion on the current state:

(mouse_position, cat_position, turn)

Then try all moves for the current player.

This seems reasonable, but the draw rule makes it subtle. A state may depend on itself through a cycle. If we mark that cycle too early as a draw, we may miss a forced win that exists through another branch.

A safer solution is to solve the game graph backward from known terminal states.

Key Insight

Every game position is a state:

(mouse, cat, turn)

where:

There are two terminal types:

1. If mouse == 0, Mouse already won.
2. If mouse == cat, Cat already won.

All other states start as unknown.

Then we propagate results backward.

This is like topological sorting on game states.

State Results

Use constants:

DRAW = 0
MOUSE_WIN = 1
CAT_WIN = 2
MOUSE_TURN = 0
CAT_TURN = 1

color[mouse][cat][turn] stores the known result of that state.

At the end, we return:

color[1][2][MOUSE_TURN]

Reverse Transitions

If we know the result of a state, we want to update its parent states.

A parent state is a state that can move into the current state in one legal move.

Suppose the current state is:

(mouse, cat, turn)

If it is Mouse’s turn now, then Cat moved previously.

So parent states are:

(mouse, previous_cat, CAT_TURN)

for every previous_cat connected to cat, except previous_cat != 0.

If it is Cat’s turn now, then Mouse moved previously.

So parent states are:

(previous_mouse, cat, MOUSE_TURN)

for every previous_mouse connected to mouse.

Degree

For each state, degree[mouse][cat][turn] means how many legal moves the player has from that state.

For Mouse’s turn:

degree[mouse][cat][MOUSE_TURN] = len(graph[mouse])

For Cat’s turn:

degree[mouse][cat][CAT_TURN] = number of neighbors of cat except 0

Degree helps detect losing states.

If all moves from a state lead to opponent wins, then this state is a win for the opponent.

Propagation Rule

When we process a known child state, we update each unknown parent.

There are two cases.

Case 1: Parent Can Move to Its Own Win

If it is Mouse’s turn in the parent and the child is MOUSE_WIN, then the parent is also MOUSE_WIN.

Mouse will choose that move.

If it is Cat’s turn in the parent and the child is CAT_WIN, then the parent is also CAT_WIN.

Cat will choose that move.

Case 2: All Moves Are Bad

If the child is a win for the opponent, then this move is bad for the player at the parent.

Reduce the parent’s degree by one.

If the degree becomes zero, every legal move leads to the opponent’s win.

So the parent is also a win for the opponent.

Algorithm

1. Create color[n][n][2], initially DRAW.
2. Create degree[n][n][2].
3. Initialize terminal states:
   • mouse == 0 means Mouse wins.
   • mouse == cat means Cat wins.
4. Push all terminal states into a queue.
5. While the queue is not empty:
   • Pop a known state.
   • Find all parent states.
   • If a parent is already known, skip it.
   • If the parent player can move into a winning result for itself, mark it.
   • Otherwise, decrement its degree.
   • If degree becomes zero, mark it as opponent win.
6. Return color[1][2][MOUSE_TURN].

Unknown states left after propagation are draws.

Correctness

Terminal states are correct by the game rules.

If Mouse is at node 0, Mouse has already won. If Cat and Mouse occupy the same node, Cat has already won.

For any non-terminal parent state, if the player to move has at least one move into a state where that same player wins, optimal play chooses that move. So the parent has the same winning result.

If every legal move from a parent leads to an opponent win, then the player to move cannot avoid losing. So the parent is a win for the opponent.

The queue processes exactly these forced consequences backward from terminal states. Any state marked by the algorithm has a forced result under optimal play.

If a state is never marked, then neither player can force a terminal win from it under these propagation rules. Such states correspond to repeated-position play, so their result remains draw.

Therefore, the result for the initial state is correct.

Complexity

Let n be the number of graph nodes.

Implementation

from collections import deque

class Solution:
    def catMouseGame(self, graph: list[list[int]]) -> int:
        DRAW = 0
        MOUSE_WIN = 1
        CAT_WIN = 2

        MOUSE_TURN = 0
        CAT_TURN = 1

        n = len(graph)

        color = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
        degree = [[[0] * 2 for _ in range(n)] for _ in range(n)]

        for mouse in range(n):
            for cat in range(n):
                degree[mouse][cat][MOUSE_TURN] = len(graph[mouse])
                degree[mouse][cat][CAT_TURN] = sum(
                    1 for next_cat in graph[cat] if next_cat != 0
                )

        queue = deque()

        for cat in range(1, n):
            for turn in (MOUSE_TURN, CAT_TURN):
                color[0][cat][turn] = MOUSE_WIN
                queue.append((0, cat, turn, MOUSE_WIN))

        for node in range(1, n):
            for turn in (MOUSE_TURN, CAT_TURN):
                color[node][node][turn] = CAT_WIN
                queue.append((node, node, turn, CAT_WIN))

        def parents(mouse: int, cat: int, turn: int):
            if turn == MOUSE_TURN:
                for previous_cat in graph[cat]:
                    if previous_cat != 0:
                        yield mouse, previous_cat, CAT_TURN
            else:
                for previous_mouse in graph[mouse]:
                    yield previous_mouse, cat, MOUSE_TURN

        while queue:
            mouse, cat, turn, result = queue.popleft()

            for prev_mouse, prev_cat, prev_turn in parents(mouse, cat, turn):
                if color[prev_mouse][prev_cat][prev_turn] != DRAW:
                    continue

                if (
                    prev_turn == MOUSE_TURN and result == MOUSE_WIN
                ) or (
                    prev_turn == CAT_TURN and result == CAT_WIN
                ):
                    color[prev_mouse][prev_cat][prev_turn] = result
                    queue.append((prev_mouse, prev_cat, prev_turn, result))
                else:
                    degree[prev_mouse][prev_cat][prev_turn] -= 1

                    if degree[prev_mouse][prev_cat][prev_turn] == 0:
                        losing_result = CAT_WIN if prev_turn == MOUSE_TURN else MOUSE_WIN
                        color[prev_mouse][prev_cat][prev_turn] = losing_result
                        queue.append((prev_mouse, prev_cat, prev_turn, losing_result))

        return color[1][2][MOUSE_TURN]

Code Explanation

The result table stores the solved outcome of each state:

color = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]

The degree table stores how many legal moves each state has:

degree = [[[0] * 2 for _ in range(n)] for _ in range(n)]

For Mouse, all adjacent nodes are legal:

degree[mouse][cat][MOUSE_TURN] = len(graph[mouse])

For Cat, node 0 is illegal:

degree[mouse][cat][CAT_TURN] = sum(
    1 for next_cat in graph[cat] if next_cat != 0
)

Terminal Mouse-win states are initialized first:

color[0][cat][turn] = MOUSE_WIN

Terminal Cat-win states are initialized when both players are on the same node:

color[node][node][turn] = CAT_WIN

The parents helper returns states that could move into the current state:

def parents(mouse: int, cat: int, turn: int):

If a parent can move to its own win, it is immediately marked as a win:

if prev_turn == MOUSE_TURN and result == MOUSE_WIN:

If the known child is bad for the parent player, we remove one available move:

degree[prev_mouse][prev_cat][prev_turn] -= 1

When no moves remain, the parent is losing:

if degree[prev_mouse][prev_cat][prev_turn] == 0:

Finally, return the initial game state:

return color[1][2][MOUSE_TURN]

Testing

def run_tests():
    s = Solution()

    assert s.catMouseGame(
        [[2, 5], [3], [0, 4, 5], [1, 4, 5], [2, 3], [0, 2, 3]]
    ) == 0

    assert s.catMouseGame(
        [[1, 3], [0], [3], [0, 2]]
    ) == 1

    assert s.catMouseGame(
        [[2], [2], [0, 1]]
    ) == 1

    assert s.catMouseGame(
        [[1, 2], [0, 2], [0, 1]]
    ) == 1

    print("all tests passed")

run_tests()

Test meaning: