# 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:

| Result | Condition |
|---|---|
| Mouse wins | Mouse reaches node `0` |
| Cat wins | Cat reaches the same node as Mouse |
| Draw | A position repeats with the same player to move |

Return:

```python
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

| Item | Meaning |
|---|---|
| Input | `graph`, an adjacency list |
| Output | `1`, `2`, or `0` |
| Mouse start | Node `1` |
| Cat start | Node `2` |
| Hole | Node `0` |
| First move | Mouse |
| Cat restriction | Cat cannot move to node `0` |

Function shape:

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

## Examples

Example 1:

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

Answer:

```python
0
```

The result is a draw with optimal play.

Example 2:

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

Answer:

```python
1
```

Mouse can force a win.

## First Thought: DFS With Memoization

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

```python
(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:

```python
(mouse, cat, turn)
```

where:

| Field | Meaning |
|---|---|
| `mouse` | Mouse position |
| `cat` | Cat position |
| `turn` | Whose turn it is |

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:

```python
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:

```python
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:

```python
(mouse, cat, turn)
```

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

So parent states are:

```python
(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:

```python
(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:

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

For Cat's turn:

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3)` | There are `O(n^2 * 2)` states, and parent enumeration costs up to `O(n)` |
| Space | `O(n^2)` | We store result and degree for each `(mouse, cat, turn)` state |

## Implementation

```python
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:

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

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

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

For Mouse, all adjacent nodes are legal:

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

For Cat, node `0` is illegal:

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

Terminal Mouse-win states are initialized first:

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

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

```python
color[node][node][turn] = CAT_WIN
```

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

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

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

```python
if prev_turn == MOUSE_TURN and result == MOUSE_WIN:
```

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

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

When no moves remain, the parent is losing:

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

Finally, return the initial game state:

```python
return color[1][2][MOUSE_TURN]
```

## Testing

```python
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:

| Test | Why |
|---|---|
| First sample | Draw under optimal play |
| Second sample | Mouse can force a win |
| Small graph with direct hole access | Mouse reaches node `0` |
| Triangle with hole | Checks Cat's restriction from entering hole |