LeetCode 1728 - Cat and Mouse II

LeetCode Problem 1728

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Graph Theory, Topological Sort, Memoization, Matrix, Game Theory

Solution

Problem Understanding

This problem describes a two-player perfect-information game played on a small grid. One player controls the mouse and the other controls the cat. Both players move optimally and alternate turns, with the mouse always moving first.

The grid contains several kinds of cells:

• 'M' represents the mouse's starting position.
• 'C' represents the cat's starting position.
• 'F' represents the food.
• '.' represents empty floor cells.
• '#' represents walls that cannot be crossed.

On each turn, the active player may move up, down, left, or right by any distance from 0 up to their jump limit. A move cannot pass through walls or leave the grid. Staying in place is also allowed.

The win conditions are asymmetric:

• If the cat lands on the mouse, the cat wins immediately.
• If the cat reaches the food first, the cat wins.
• If the mouse reaches the food first, the mouse wins.
• If the game continues too long and the mouse does not reach the food within 1000 turns, the cat automatically wins.

The task is to determine whether the mouse can force a win assuming both sides play optimally.

The constraints are small:

• Grid dimensions are at most 8 x 8.
• Total cells are at most 64.
• Jump distances are at most 8.

Even though the board is small, the game state space is large because each state depends on:

• Mouse position
• Cat position
• Whose turn it is

Additionally, cycles are possible because players can stay in place or revisit positions. That means naive recursion can easily loop forever unless carefully controlled.

Several edge cases are important:

• The mouse or cat may already have a direct path to the food.
• Staying still may be strategically optimal.
• Walls can completely block movement.
• The cat can win simply by preventing the mouse from reaching food for too long.
• Cyclic game states must be handled correctly.
• Multiple paths with different jump lengths must all be considered.

This is fundamentally a game theory problem on a directed state graph.

Approaches

Brute Force Approach

The most straightforward solution is to simulate every possible game recursively using minimax style search.

For each state:

• If it is the mouse's turn, try every legal mouse move.
• If it is the cat's turn, try every legal cat move.
• Continue recursively until someone wins.

This produces the correct answer conceptually because it explores the full game tree under optimal play.

However, the problem is that the game graph contains cycles. Players can revisit the same positions repeatedly, especially because staying still is allowed. Without careful memoization and cycle handling, recursion can become infinite.

Even with memoization, the branching factor is large because every state may generate many possible jumps. The additional 1000-turn rule also complicates recursion because the outcome may depend on move count.

A naive brute force search becomes impractical.

Optimal Approach

The key insight is that this is a finite impartial game that can be modeled as a graph of states.

A state consists of:

• Mouse position
• Cat position
• Turn indicator

Each state transitions to other states according to valid moves.

Instead of solving forward recursively, we solve backward using reverse graph propagation and topological game analysis.

This technique is similar to retrograde analysis used in chess endgames.

The idea is:

• Mark terminal winning states first.
• Propagate results backward.
• If a player can move into a winning state for themselves, then the current state is winning.
• If every possible move leads to the opponent winning, then the current state is losing.

This avoids infinite recursion because states are processed systematically.

The number of states is manageable:

• At most 64 * 64 * 2 = 8192 states.

That makes graph-based dynamic programming feasible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible game paths recursively
Optimal	O(N² × D)	O(N²)	Reverse BFS on game states with memoized outcomes

Here:

• N is the number of walkable cells
• D is the maximum number of legal moves from a state

Algorithm Walkthrough

Step 1: Encode Walkable Cells

First, scan the grid and assign an integer index to every non-wall cell.

This simplifies state storage because positions can now be represented as integers instead of coordinate pairs.

We also record:

• Mouse start position
• Cat start position
• Food position

Step 2: Precompute Legal Moves

For every cell, precompute all valid destinations for:

• Mouse movement
• Cat movement

This includes:

• Staying in place
• Jumping any distance from 1 to jump limit
• Stopping before walls

Precomputing moves avoids repeated grid traversal during the game analysis.

Step 3: Define Game States

A state is represented as:

(mouse_position, cat_position, turn)

where:

• turn = 0 means mouse turn
• turn = 1 means cat turn

For each state we store:

• Result status

• Unknown

• Mouse win

• Cat win

• Remaining degree

• Number of legal moves available

The degree is important for backward propagation.

Step 4: Initialize Terminal States

Some states have immediate known outcomes.

If mouse and cat occupy the same cell:

• Cat wins immediately.

If cat reaches food:

• Cat wins immediately.

If mouse reaches food:

• Mouse wins immediately.

These states become the starting points of the reverse BFS.

Step 5: Build Reverse State Propagation

We process states backward.

Suppose we know a state is winning for the mouse.

Then any previous mouse-turn state that can move into this state is also winning for the mouse.

Similarly:

• If every move from a state leads to opponent victory, that state becomes losing.

To support this efficiently, we compute parent states dynamically.

Step 6: Reverse BFS

We use a queue containing resolved states.

For each resolved state:

1. Find all predecessor states.
2. If the predecessor's current player can move into a winning state for themselves:

• Mark predecessor as winning.

3. Otherwise reduce its remaining degree.
4. If degree becomes zero:

• All moves lose, so mark it as opponent victory.

This is the standard game graph retrograde propagation technique.

Step 7: Return Initial State Result

Finally, inspect:

(mouse_start, cat_start, mouse_turn)

If this state is marked as mouse win:

• Return True

Otherwise:

• Return False

Why it works

The algorithm works because every state is classified according to optimal play.

A state is winning for a player if that player can force the game into a state already known to be winning for them. A state is losing if every legal move leads to an opponent-winning state.

Reverse BFS guarantees that states are resolved only after enough information is available. Since the game graph is finite, every reachable state eventually receives the correct classification.

Python Solution

from collections import deque
from typing import List

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        rows = len(grid)
        cols = len(grid[0])

        positions = []
        pos_to_id = {}

        mouse_start = 0
        cat_start = 0
        food = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != '#':
                    idx = len(positions)
                    positions.append((r, c))
                    pos_to_id[(r, c)] = idx

                    if grid[r][c] == 'M':
                        mouse_start = idx
                    elif grid[r][c] == 'C':
                        cat_start = idx
                    elif grid[r][c] == 'F':
                        food = idx

        n = len(positions)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def build_moves(jump_limit: int):
            moves = [[] for _ in range(n)]

            for i, (r, c) in enumerate(positions):
                moves[i].append(i)

                for dr, dc in directions:
                    for step in range(1, jump_limit + 1):
                        nr = r + dr * step
                        nc = c + dc * step

                        if not (0 <= nr < rows and 0 <= nc < cols):
                            break

                        if grid[nr][nc] == '#':
                            break

                        moves[i].append(pos_to_id[(nr, nc)])

            return moves

        mouse_moves = build_moves(mouseJump)
        cat_moves = build_moves(catJump)

        MOUSE_TURN = 0
        CAT_TURN = 1

        UNKNOWN = 0
        MOUSE_WIN = 1
        CAT_WIN = 2

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

        for m in range(n):
            for c in range(n):
                degree[m][c][MOUSE_TURN] = len(mouse_moves[m])
                degree[m][c][CAT_TURN] = len(cat_moves[c])

        queue = deque()

        for pos in range(n):
            for turn in range(2):
                if pos != food:
                    result[pos][pos][turn] = CAT_WIN
                    queue.append((pos, pos, turn, CAT_WIN))

                result[food][pos][turn] = MOUSE_WIN
                queue.append((food, pos, turn, MOUSE_WIN))

                if pos != food:
                    result[pos][food][turn] = CAT_WIN
                    queue.append((pos, food, turn, CAT_WIN))

        def parents(mouse_pos: int, cat_pos: int, turn: int):
            if turn == MOUSE_TURN:
                for prev_cat in cat_moves[cat_pos]:
                    yield mouse_pos, prev_cat, CAT_TURN
            else:
                for prev_mouse in mouse_moves[mouse_pos]:
                    yield prev_mouse, cat_pos, MOUSE_TURN

        while queue:
            mouse_pos, cat_pos, turn, state_result = queue.popleft()

            for pm, pc, pt in parents(mouse_pos, cat_pos, turn):
                if result[pm][pc][pt] != UNKNOWN:
                    continue

                if (
                    pt == MOUSE_TURN and state_result == MOUSE_WIN
                ) or (
                    pt == CAT_TURN and state_result == CAT_WIN
                ):
                    result[pm][pc][pt] = state_result
                    queue.append((pm, pc, pt, state_result))
                else:
                    degree[pm][pc][pt] -= 1

                    if degree[pm][pc][pt] == 0:
                        loser_result = (
                            CAT_WIN if pt == MOUSE_TURN else MOUSE_WIN
                        )

                        result[pm][pc][pt] = loser_result
                        queue.append((pm, pc, pt, loser_result))

        return result[mouse_start][cat_start][MOUSE_TURN] == MOUSE_WIN

The implementation begins by converting every walkable cell into a compact integer identifier. This allows all game states to be indexed efficiently using arrays instead of hash maps.

Next, the solution precomputes every legal movement for both the mouse and the cat. Because the jump distance differs between the two players, two separate move tables are built.

The result array stores the outcome of every possible state. Initially, all states are unknown. The degree array tracks how many legal moves remain unresolved from each state.

Terminal winning states are then initialized:

• Mouse at food means mouse win.
• Cat at food means cat win.
• Cat catching mouse means cat win.

These known states are inserted into the BFS queue.

The parents() generator computes reverse edges dynamically. Instead of storing the reverse graph explicitly, predecessor states are generated when needed.

During BFS propagation:

• If a player can move into a winning state for themselves, the predecessor becomes winning immediately.
• Otherwise, one legal move is eliminated.
• If no moves remain, the state becomes losing.

Finally, the algorithm checks whether the initial game state is classified as a mouse win.

Go Solution

package main

import "container/list"

func canMouseWin(grid []string, catJump int, mouseJump int) bool {
	rows := len(grid)
	cols := len(grid[0])

	type Pair struct {
		r int
		c int
	}

	positions := []Pair{}
	posToID := map[Pair]int{}

	mouseStart := 0
	catStart := 0
	food := 0

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] != '#' {
				id := len(positions)
				positions = append(positions, Pair{r, c})
				posToID[Pair{r, c}] = id

				if grid[r][c] == 'M' {
					mouseStart = id
				} else if grid[r][c] == 'C' {
					catStart = id
				} else if grid[r][c] == 'F' {
					food = id
				}
			}
		}
	}

	n := len(positions)

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	buildMoves := func(jumpLimit int) [][]int {
		moves := make([][]int, n)

		for i, p := range positions {
			moves[i] = append(moves[i], i)

			for _, d := range directions {
				for step := 1; step <= jumpLimit; step++ {
					nr := p.r + d[0]*step
					nc := p.c + d[1]*step

					if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
						break
					}

					if grid[nr][nc] == '#' {
						break
					}

					moves[i] = append(moves[i], posToID[Pair{nr, nc}])
				}
			}
		}

		return moves
	}

	mouseMoves := buildMoves(mouseJump)
	catMoves := buildMoves(catJump)

	const (
		MOUSE_TURN = 0
		CAT_TURN   = 1

		UNKNOWN    = 0
		MOUSE_WIN  = 1
		CAT_WIN    = 2
	)

	result := make([][][]int, n)
	degree := make([][][]int, n)

	for i := 0; i < n; i++ {
		result[i] = make([][]int, n)
		degree[i] = make([][]int, n)

		for j := 0; j < n; j++ {
			result[i][j] = make([]int, 2)
			degree[i][j] = make([]int, 2)

			degree[i][j][MOUSE_TURN] = len(mouseMoves[i])
			degree[i][j][CAT_TURN] = len(catMoves[j])
		}
	}

	type State struct {
		mouse int
		cat   int
		turn  int
		res   int
	}

	queue := list.New()

	for pos := 0; pos < n; pos++ {
		for turn := 0; turn < 2; turn++ {

			if pos != food {
				result[pos][pos][turn] = CAT_WIN
				queue.PushBack(State{pos, pos, turn, CAT_WIN})
			}

			result[food][pos][turn] = MOUSE_WIN
			queue.PushBack(State{food, pos, turn, MOUSE_WIN})

			if pos != food {
				result[pos][food][turn] = CAT_WIN
				queue.PushBack(State{pos, food, turn, CAT_WIN})
			}
		}
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		cur := front.Value.(State)

		mousePos := cur.mouse
		catPos := cur.cat
		turn := cur.turn
		stateResult := cur.res

		if turn == MOUSE_TURN {

			for _, prevCat := range catMoves[catPos] {

				pm := mousePos
				pc := prevCat
				pt := CAT_TURN

				if result[pm][pc][pt] != UNKNOWN {
					continue
				}

				if stateResult == CAT_WIN {
					result[pm][pc][pt] = CAT_WIN
					queue.PushBack(State{pm, pc, pt, CAT_WIN})
				} else {
					degree[pm][pc][pt]--

					if degree[pm][pc][pt] == 0 {
						result[pm][pc][pt] = MOUSE_WIN
						queue.PushBack(State{pm, pc, pt, MOUSE_WIN})
					}
				}
			}

		} else {

			for _, prevMouse := range mouseMoves[mousePos] {

				pm := prevMouse
				pc := catPos
				pt := MOUSE_TURN

				if result[pm][pc][pt] != UNKNOWN {
					continue
				}

				if stateResult == MOUSE_WIN {
					result[pm][pc][pt] = MOUSE_WIN
					queue.PushBack(State{pm, pc, pt, MOUSE_WIN})
				} else {
					degree[pm][pc][pt]--

					if degree[pm][pc][pt] == 0 {
						result[pm][pc][pt] = CAT_WIN
						queue.PushBack(State{pm, pc, pt, CAT_WIN})
					}
				}
			}
		}
	}

	return result[mouseStart][catStart][MOUSE_TURN] == MOUSE_WIN
}

The Go implementation follows the same algorithmic structure as the Python solution.

The main difference is memory handling. Go requires explicit allocation of multidimensional slices, so the result and degree arrays are initialized layer by layer.

Go also lacks Python generators, so predecessor traversal is written inline during BFS propagation.

The queue is implemented using container/list, which provides efficient push and pop operations from both ends.

Since all state values fit comfortably inside standard integers, overflow is not a concern.

Worked Examples

Example 1

grid = ["####F",
        "#C...",
        "M...."]

catJump = 1
mouseJump = 2

Initial Positions

Entity	Position
Mouse	bottom-left
Cat	middle row
Food	top-right

The mouse can move up to 2 cells each turn.

The cat can move only 1 cell.

Key Observation

The cat is separated from the food by walls and cannot intercept quickly enough.

State Expansion

Initial state:

Mouse	Cat	Turn
M0	C0	Mouse

The mouse explores legal jumps:

Move	Result
Stay	Too slow
Move right	Progress toward food
Move upward	Avoid cat

Eventually the reverse BFS marks the initial state as MOUSE_WIN.

Final answer:

true

Example 2

grid = ["M.C...F"]

catJump = 1
mouseJump = 4

The mouse can jump extremely far in one move.

First Mouse Turn

Mouse immediately moves near or directly to the food before the cat can interfere.

The state graph quickly propagates mouse-winning states backward.

Final answer:

true

Example 3

grid = ["M.C...F"]

catJump = 1
mouseJump = 3

Now the mouse cannot reach the food quickly enough.

The cat can position itself to block or capture.

During backward propagation:

• Every mouse move eventually leads to cat-winning states.
• The initial state becomes CAT_WIN.

Final answer:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N² × D)	Each state and transition is processed at most once
Space	O(N²)	Stores results and degrees for all game states

Here:

• N is the number of walkable cells, at most 64
• D is the maximum number of legal moves from a cell

The total number of states is:

N × N × 2

which is at most about 8192.

Each state processes a bounded number of transitions, so the algorithm comfortably fits within limits.

Test Cases

sol = Solution()

# Example 1
assert sol.canMouseWin(
    ["####F",
     "#C...",
     "M...."],
    1,
    2
) == True  # mouse reaches food safely

# Example 2
assert sol.canMouseWin(
    ["M.C...F"],
    1,
    4
) == True  # mouse can jump directly toward food

# Example 3
assert sol.canMouseWin(
    ["M.C...F"],
    1,
    3
) == False  # cat can stop mouse

# Mouse already near food
assert sol.canMouseWin(
    ["MF.C"],
    1,
    1
) == True  # mouse wins immediately

# Cat controls food
assert sol.canMouseWin(
    ["MCF"],
    1,
    1
) == False  # cat blocks access

# Walls restrict movement
assert sol.canMouseWin(
    ["M#F",
     ".#.",
     "C.."],
    1,
    2
) == False  # walls trap mouse path

# Large jump advantage
assert sol.canMouseWin(
    ["M....F",
     "......",
     "..C..."],
    1,
    8
) == True  # mouse mobility dominates

# Cat starts near mouse
assert sol.canMouseWin(
    ["MCF"],
    2,
    1
) == False  # cat immediately threatens mouse

# Tight maze
assert sol.canMouseWin(
    ["M..#F",
     ".#.#.",
     ".#C#.",
     "....."],
    1,
    2
) in [True, False]  # stress complex state graph

Test Summary

Test	Why
Example 1	Verifies basic mouse win
Example 2	Verifies long mouse jump
Example 3	Verifies cat defensive strategy
Mouse near food	Tests immediate win
Cat controls food	Tests blocking behavior
Walls restrict movement	Tests obstacle handling
Large jump advantage	Tests mobility dominance
Cat near mouse	Tests immediate capture pressure
Tight maze	Tests complex cyclic states

Edge Cases

One important edge case occurs when the mouse can reach the food immediately on its first move. A naive implementation may continue searching unnecessarily instead of recognizing the instant win condition. This solution handles that correctly because all terminal states involving the mouse at the food are initialized before BFS propagation begins.

Another tricky case involves cycles. Since both players are allowed to stay still, the game graph can contain many loops. Recursive DFS solutions frequently fail here due to infinite recursion or incorrect memoization. The reverse BFS approach avoids this entirely because every state is processed finitely through graph propagation.

Walls create another subtle issue. Players cannot jump through walls, even if their jump distance would normally allow it. Incorrect implementations sometimes allow movement past blocked cells. This solution explicitly stops movement generation as soon as a wall is encountered, ensuring every generated move is valid.

A final edge case involves the cat reaching the food before the mouse. Some implementations focus only on direct captures and forget that the cat wins by occupying the food as well. The initialization phase explicitly marks every state where the cat is on the food as a cat victory, guaranteeing correct propagation.