1728. Cat and Mouse II - Solution & Explanation

Q: Is Cat and Mouse II easy or hard?

Cat and Mouse II is classified as a Hard problem on LeetCode. It requires combining grid traversal, game theory reasoning, dynamic programming over states, and careful handling of cycles or repeated positions.

Q: Cat and Mouse II Python/Java solution

Python implementations usually use DFS with memoization and a state cache keyed by mouse position, cat position, and turn. Java and C++ solutions often implement BFS with state tracking and degree counting to perform retrograde analysis over the game graph.

Q: How to solve Cat and Mouse II in O(n)?

An O(n) solution is not feasible because the game state depends on both mouse and cat positions. The minimum state space is roughly (m*n)^2 with an additional turn dimension. Efficient solutions reduce the search using memoization or BFS-based retrograde analysis over the state graph.

Q: What is the best approach for Cat and Mouse II?

The most common approach is minimax with memoization. Each game state is defined by the mouse position, cat position, and whose turn it is. DFS explores all possible moves while caching results to avoid recomputation. This converts the adversarial game into a dynamic programming problem over states.

Q: Is Cat and Mouse II asked at Google/Amazon/Meta?

Game theory and adversarial search problems like Cat and Mouse II appear in interviews at companies such as Google, Meta, and Amazon. While the exact problem may not appear frequently, the techniques—minimax search, memoization, and graph state modeling—are common interview topics.

Q: What data structure is used in Cat and Mouse II?

The solution relies on grids, graph-style state representations, and memoization tables or DP arrays. DFS recursion with caching or BFS queues are typically used to evaluate game states and propagate winning or losing outcomes.

Q: What is the time complexity of Cat and Mouse II?

The typical solution runs in about O((m*n)^2 * K), where m*n represents grid cells and K is the maximum number of turns considered (often capped near 1000). The state space includes mouse position, cat position, and turn. Memoization or BFS state pruning prevents exponential exploration.

The problem

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

Players are represented by the characters 'C'(Cat),'M'(Mouse).
Floors are represented by the character '.' and can be walked on.
Walls are represented by the character '#' and cannot be walked on.
Food is represented by the character 'F' and can be walked on.
There is only one of each character 'C', 'M', and 'F' in grid.

Mouse and Cat play according to the following rules:

Mouse moves first, then they take turns to move.
During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
Staying in the same position is allowed.
Mouse can jump over Cat.

The game can end in 4 ways:

If Cat occupies the same position as Mouse, Cat wins.
If Cat reaches the food first, Cat wins.
If Mouse reaches the food first, Mouse wins.
If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.

Example 1:

Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
Output: true
Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 4
Output: true

Example 3:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
Output: false

Constraints:

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
There is only one of each character 'C', 'M', and 'F' in grid.
1 <= catJump, mouseJump <= 8

Approach overview

Problem Overview: A mouse and a cat move on a grid containing walls, food, and empty cells. The mouse moves first and both players can jump several cells in one direction. The mouse wins if it reaches the food, the cat wins if it catches the mouse or reaches the food first. The challenge is determining whether the mouse can force a win assuming both players play optimally.

Approach 1: Minimax with Memoization (Game DFS) (Time: O((mn)^2 * K), Space: O((mn)^2 * K))

This approach models the game as a recursive minimax search. Each state is defined by the mouse position, cat position, and whose turn it is. From a state, generate all valid moves by iterating up to the maximum jump distance in the four directions until hitting a wall. The mouse tries to reach the food or move into a state where the cat eventually loses, while the cat tries to capture the mouse or force a losing state for the mouse. Use memoization to cache results for previously evaluated states to avoid exponential recomputation. A move counter (usually capped around 1000 turns) prevents infinite loops. This turns a huge game tree into a manageable dynamic programming problem over states. The technique combines ideas from game theory and dynamic programming.

Approach 2: Breadth-First Search with State Tracking (Retrograde Analysis) (Time: O((mn)^2 * K), Space: O((mn)^2 * K))

This solution treats the game as a directed graph where each node represents a full state: (mousePosition, catPosition, turn). Instead of exploring forward, it performs retrograde analysis using BFS from known terminal states. Terminal states include the mouse reaching food (mouse win) or the cat catching the mouse (cat win). Maintain degree counts for each state representing how many moves are still unresolved. When a state is determined to be winning for one player, propagate that result backward to predecessor states. If all moves from a predecessor lead to opponent wins, that state becomes a loss. This technique resembles topological sorting on the state graph and avoids deep recursion. It works well for large state spaces typical in graph game problems.

Recommended for interviews: Minimax with memoization is the most intuitive approach and clearly demonstrates understanding of game states and optimal play. Interviewers often expect you to identify the state definition and apply DFS with caching. The BFS retrograde method is more advanced and efficient for reasoning about large game graphs, showing deeper understanding of graph processing and competitive game analysis.

Approach 1: Minimax with Memoization

In this approach, we use a recursive minimax strategy with memoization to simulate the game turns. The strategy checks all possible moves for both players and assumes that they play optimally. The goal is to determine if there is a path that allows the Mouse to win before the Cat can win.

We recursively compute the result for each state — characterized by the positions of Cat, Mouse, and the turn number — and store the results to avoid redundant computations.

Python

# Python code for Minimax with Memoization
from functools import lru_cache

def canMouseWin(grid, catJump, mouseJump):
    # Parse the grid
    rows, cols = len(grid), len(grid[0])
    cat_pos, mouse_pos, food_pos = None, None, None
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 'C':
                cat_pos = (r, c)
            elif grid[r][c] == 'M':
                mouse_pos = (r, c)
            elif grid[r][c] == 'F':
                food_pos = (r, c)

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

    @lru_cache(None)
    def dp(turn, cat_r, cat_c, mouse_r, mouse_c):
        if turn == 1000:
            return False

        if (cat_r, cat_c) == food_pos or (cat_r, cat_c) == (mouse_r, mouse_c):
            return False
        if (mouse_r, mouse_c) == food_pos:
            return True

        mouse_turn = turn % 2 == 0

        for dr, dc in directions:
            for jump in range(1, (mouseJump if mouse_turn else catJump) + 1):
                new_r, new_c = (mouse_r, mouse_c) if mouse_turn else (cat_r, cat_c)
                new_r += dr * jump
                new_c += dc * jump

                if 0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] != '#':
                    if mouse_turn:
                        if dp(turn + 1, cat_r, cat_c, new_r, new_c):
                            return True
                    else:
                        if not dp(turn + 1, new_r, new_c, mouse_r, mouse_c):
                            return False
                else:
                    break

        return not mouse_turn

    return dp(0, cat_pos[0], cat_pos[1], mouse_pos[0], mouse_pos[1])

JavaScript

// JavaScript code for Minimax with Memoization
function canMouseWin(grid, catJump, mouseJump) {
    const rows = grid.length;
    const cols = grid[0].length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    let catPos, mousePos, foodPos;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 'C') catPos = [r, c];
            else if (grid[r][c] === 'M') mousePos = [r, c];
            else if (grid[r][c] === 'F') foodPos = [r, c];
        }
    }

    const dp = new Map();

    function hash(turn, cr, cc, mr, mc) {
        return `${turn},${cr},${cc},${mr},${mc}`;
    }

    function search(turn, cr, cc, mr, mc) {
        if (turn === 1000) return false;
        if ((cr === foodPos[0] && cc === foodPos[1]) || (cr === mr && cc === mc)) return false;
        if (mr === foodPos[0] && mc === foodPos[1]) return true;

        const state = hash(turn, cr, cc, mr, mc);
        if (dp.has(state)) return dp.get(state);

        const mouseTurn = turn % 2 === 0;
        let canWin = false;

        for (const [dr, dc] of directions) {
            const limit = mouseTurn ? mouseJump : catJump;
            for (let jump = 0; jump <= limit; jump++) {
                const [nr, nc] = mouseTurn ? [mr + dr * jump, mc + dc * jump] : [cr + dr * jump, cc + dc * jump];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === '#') break;

                if (mouseTurn) {
                    if (search(turn + 1, cr, cc, nr, nc)) {
                        canWin = true;
                        break;
                    }
                } else {
                    if (!search(turn + 1, nr, nc, mr, mc)) {
                        canWin = true;
                        break;
                    }
                }
            }
            if (canWin) break;
        }

        dp.set(state, canWin);
        return canWin;
    }

    return search(0, catPos[0], catPos[1], mousePos[0], mousePos[1]);
}

This solution uses a DFS-like approach with memoization to minimize repeated calculations. We first parse the grid to find the initial positions of the cat, mouse, and food. The recursive function dp simulates the game, considering moves for both players and deciding the result of the game with optimal play from both sides. The memoization is achieved using the lru_cache decorator, which stores the result of each state configuration.

Complexity

Time Complexity: O(n^4) due to recursive state space exploration up to a depth of 1000 moves potential.

Space Complexity: O(n^4) because of memoization of the states, where n is the number of grid cells.

Try this approach in the editor

Approach 2: Breadth-First Search with State Tracking

In this approach, we use a Breadth-First Search (BFS) strategy to systematically explore the game states. By using a queue to store each game state, we can track the minimum number of moves needed for the Mouse to reach the food while avoiding the Cat.

Each state is represented by the positions of the Cat, Mouse, and the number of turns, ensuring that we explore all possible moves within 1000 turns. We keep track of visited states to reduce redundant processing.

Java

// Java code for Breadth-First Search with State Tracking
import java.util.*;

public class CatMouseGame {
    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        int rows = grid.length;
        int cols = grid[0].length();
        int[] catPos = new int[2], mousePos = new int[2], foodPos = new int[2];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r].charAt(c) == 'C') {
                    catPos = new int[]{r, c};
                } else if (grid[r].charAt(c) == 'M') {
                    mousePos = new int[]{r, c};
                } else if (grid[r].charAt(c) == 'F') {
                    foodPos = new int[]{r, c};
                }
            }
        }

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, catPos[0], catPos[1], mousePos[0], mousePos[1]});

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int turn = state[0];
            int cr = state[1], cc = state[2], mr = state[3], mc = state[4];
            if (turn >= 1000) return false;
            if ((cr == foodPos[0] && cc == foodPos[1]) || (cr == mr && cc == mc)) return false;
            if (mr == foodPos[0] && mc == foodPos[1]) return true;

            String stateKey = cr + "," + cc + "," + mr + "," + mc + "," + turn;
            if (!visited.add(stateKey)) continue;

            boolean mouseTurn = turn % 2 == 0;
            for (int[] dir : directions) {
                int limit = mouseTurn ? mouseJump : catJump;
                for (int jump = 0; jump <= limit; jump++) {
                    int newRow = mouseTurn ? mr + dir[0] * jump : cr + dir[0] * jump;
                    int newCol = mouseTurn ? mc + dir[1] * jump : cc + dir[1] * jump;

                    if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || grid[newRow].charAt(newCol) == '#') break;

                    if (mouseTurn) {
                        queue.offer(new int[]{turn + 1, cr, cc, newRow, newCol});
                    } else {
                        queue.offer(new int[]{turn + 1, newRow, newCol, mr, mc});
                    }
                }
            }
        }
        return false;
    }
}

C++

// C++ code for Breadth-First Search with State Tracking
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        int rows = grid.size();
        int cols = grid[0].size();
        pair<int, int> catPos, mousePos, foodPos;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 'C') {
                    catPos = {r, c};
                } else if (grid[r][c] == 'M') {
                    mousePos = {r, c};
                } else if (grid[r][c] == 'F') {
                    foodPos = {r, c};
                }
            }
        }

        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        unordered_set<string> visited;
        queue<tuple<int, int, int, int, int>> q;
        q.push({0, catPos.first, catPos.second, mousePos.first, mousePos.second});

        while (!q.empty()) {
            auto [turn, cr, cc, mr, mc] = q.front(); q.pop();

            if (turn >= 1000) return false;
            if ((cr == foodPos.first && cc == foodPos.second) || (cr == mr && cc == mc)) return false;
            if (mr == foodPos.first && mc == foodPos.second) return true;

            string stateKey = to_string(cr) + "," + to_string(cc) + "," + to_string(mr) + "," + to_string(mc) + "," + to_string(turn);
            if (!visited.insert(stateKey).second) continue;

            bool mouseTurn = turn % 2 == 0;
            int jumpLimit = mouseTurn ? mouseJump : catJump;

            for (const auto& dir : directions) {
                for (int jump = 0; jump <= jumpLimit; ++jump) {
                    int new_r = mouseTurn ? mr + dir.first * jump : cr + dir.first * jump;
                    int new_c = mouseTurn ? mc + dir.second * jump : cc + dir.second * jump;

                    if (new_r < 0 || new_r >= rows || new_c < 0 || new_c >= cols || grid[new_r][new_c] == '#') break;

                    if (mouseTurn) {
                        q.push({turn + 1, cr, cc, new_r, new_c});
                    } else {
                        q.push({turn + 1, new_r, new_c, mr, mc});
                    }
                }
            }
        }
        return false;
    }
};

This Java code implements a BFS strategy using a queue to explore each possible state. We parse the grid to identify initial positions, enqueuing the initial state. By exploring each direction for both cat and mouse moves, while considering optimal moves, we determine the earliest possible win condition for the Mouse.

Complexity

Time Complexity: O(n^4) as we explore potential grid configurations extensively within the move constraint.

Space Complexity: O(n^4) because of the queue storage for state exploration.

Try this approach in the editor

Approach 3: Topological Sorting

According to the problem description, the state of the game is determined by the mouse's position, the cat's position, and whose turn it is. The following states can be determined directly:

When the cat and the mouse are at the same position, the cat wins — this is a winning state for the cat and a losing state for the mouse.
When the cat reaches the food first, the cat wins — this is a winning state for the cat and a losing state for the mouse.
When the mouse reaches the food first, the mouse wins — this is a winning state for the mouse and a losing state for the cat.

To determine the result of the initial state, we need to traverse all states starting from the boundary states. Each state contains the mouse's position, the cat's position, and whose turn it is. From the current state, we can derive all possible previous states: the mover in the previous state is the opposite of the current mover, and the mover's position in the previous state differs from that in the current state.

We use the tuple (m, c, t) to represent the current state, and (pm, pc, pt) to represent a possible previous state. All possible previous states are:

If the current mover is the mouse, then the previous mover was the cat, the mouse's position in the previous state equals the current mouse position, and the cat's position in the previous state is any neighbor of the current cat position.
If the current mover is the cat, then the previous mover was the mouse, the cat's position in the previous state equals the current cat position, and the mouse's position in the previous state is any neighbor of the current mouse position.

Initially, except for the boundary states, the results of all other states are unknown. Starting from the boundary states, for each state we derive all possible previous states and update their results according to the following logic:

If the previous mover is the same as the current winner, then the previous mover can reach the current state and win — directly update the previous state to the current winner.
If the previous mover is different from the current winner, and all states reachable by the previous mover are losing states for the previous mover, then we update the previous state to the current winner.

For the second update rule, we need to record the degree of each state. Initially, the degree of a state represents the number of nodes the mover of that state can move to, i.e., the number of neighbors of the node where the mover is located. If the mover is the cat and the cat's node is adjacent to the hole, the degree of that state should be decremented by 1.

When all states have been updated, the result of the initial state is the final answer.

The time complexity is O(m^2 times n^2 times (m + n)) and the space complexity is O(m^2 times n^2), where m and n are the number of rows and columns of the grid, respectively.

TypeScript

function canMouseWin(grid: string[], catJump: number, mouseJump: number): boolean {
    const m = grid.length;
    const n = grid[0].length;

    let catStart = 0;
    let mouseStart = 0;
    let food = 0;

    const dirs = [-1, 0, 1, 0, -1];

    const gMouse: number[][] = Array.from({ length: m * n }, () => []);
    const gCat: number[][] = Array.from({ length: m * n }, () => []);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const c = grid[i][j];

            if (c === '#') continue;

            const v = i * n + j;

            if (c === 'C') catStart = v;
            else if (c === 'M') mouseStart = v;
            else if (c === 'F') food = v;

            for (let d = 0; d < 4; d++) {
                const a = dirs[d];
                const b = dirs[d + 1];

                for (let k = 0; k <= mouseJump; k++) {
                    const x = i + k * a;
                    const y = j + k * b;

                    if (!(0 <= x && x < m && 0 <= y && y < n && grid[x][y] !== '#')) break;

                    gMouse[v].push(x * n + y);
                }

                for (let k = 0; k <= catJump; k++) {
                    const x = i + k * a;
                    const y = j + k * b;

                    if (!(0 <= x && x < m && 0 <= y && y < n && grid[x][y] !== '#')) break;

                    gCat[v].push(x * n + y);
                }
            }
        }
    }

    function getPrevStates(m: number, c: number, t: number, ans: number[][][]): number[][] {
        const pt = t ^ 1;
        const pre: number[][] = [];

        if (pt === 1) {
            for (const pc of gCat[c]) {
                if (ans[m][pc][1] === 0) pre.push([m, pc, pt]);
            }
        } else {
            for (const pm of gMouse[m]) {
                if (ans[pm][c][0] === 0) pre.push([pm, c, pt]);
            }
        }

        return pre;
    }

    function calc(): number {
        const N = m * n;

        const degree: number[][][] = Array.from({ length: N }, () =>
            Array.from({ length: N }, () => [0, 0]),
        );

        const ans: number[][][] = Array.from({ length: N }, () =>
            Array.from({ length: N }, () => [0, 0]),
        );

        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                degree[i][j][0] = gMouse[i].length;
                degree[i][j][1] = gCat[j].length;
            }
        }

        const q: number[][] = [];

        for (let i = 0; i < N; i++) {
            ans[food][i][1] = 1;
            ans[i][food][0] = 2;
            ans[i][i][1] = 2;
            ans[i][i][0] = 2;

            q.push([food, i, 1]);
            q.push([i, food, 0]);
            q.push([i, i, 0]);
            q.push([i, i, 1]);
        }

        while (q.length) {
            const [mPos, cPos, t] = q.shift()!;
            const currentAns = ans[mPos][cPos][t];

            for (const [pm, pc, pt] of getPrevStates(mPos, cPos, t, ans)) {
                if (pt === currentAns - 1) {
                    ans[pm][pc][pt] = currentAns;
                    q.push([pm, pc, pt]);
                } else {
                    degree[pm][pc][pt]--;
                    if (degree[pm][pc][pt] === 0) {
                        ans[pm][pc][pt] = currentAns;
                        q.push([pm, pc, pt]);
                    }
                }
            }
        }

        return ans[mouseStart][catStart][0];
    }

    return calc() === 1;
}

func canMouseWin(grid []string, catJump int, mouseJump int) bool {
	m, n := len(grid), len(grid[0])
	catStart, mouseStart, food := 0, 0, 0
	dirs := []int{-1, 0, 1, 0, -1}
	gMouse := make([][]int, m*n)
	gCat := make([][]int, m*n)

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			c := grid[i][j]
			if c == '#' {
				continue
			}
			v := i*n + j
			if c == 'C' {
				catStart = v
			} else if c == 'M' {
				mouseStart = v
			} else if c == 'F' {
				food = v
			}
			for d := 0; d < 4; d++ {
				a, b := dirs[d], dirs[d+1]
				for k := 0; k <= mouseJump; k++ {
					x, y := i+k*a, j+k*b
					if !(0 <= x && x < m && 0 <= y && y < n && grid[x][y] != '#') {
						break
					}
					gMouse[v] = append(gMouse[v], x*n+y)
				}
				for k := 0; k <= catJump; k++ {
					x, y := i+k*a, j+k*b
					if !(0 <= x && x < m && 0 <= y && y < n && grid[x][y] != '#') {
						break
					}
					gCat[v] = append(gCat[v], x*n+y)
				}
			}
		}
	}
	return calc(gMouse, gCat, mouseStart, catStart, food) == 1
}

func calc(gMouse, gCat [][]int, mouseStart, catStart, hole int) int {
	n := len(gMouse)
	degree := make([][][]int, n)
	ans := make([][][]int, n)
	for i := 0; i < n; i++ {
		degree[i] = make([][]int, n)
		ans[i] = make([][]int, n)
		for j := 0; j < n; j++ {
			degree[i][j] = make([]int, 2)
			ans[i][j] = make([]int, 2)
			degree[i][j][0] = len(gMouse[i])
			degree[i][j][1] = len(gCat[j])
		}
	}

	q := list.New()
	for i := 0; i < n; i++ {
		ans[hole][i][1] = 1
		ans[i][hole][0] = 2
		ans[i][i][1] = 2
		ans[i][i][0] = 2
		q.PushBack([]int{hole, i, 1})
		q.PushBack([]int{i, hole, 0})
		q.PushBack([]int{i, i, 0})
		q.PushBack([]int{i, i, 1})
	}

	for q.Len() > 0 {
		front := q.Front()
		q.Remove(front)
		state := front.Value.([]int)
		m, c, t := state[0], state[1], state[2]
		currentAns := ans[m][c][t]
		for _, prevState := range getPrevStates(gMouse, gCat, m, c, t, ans) {
			pm, pc, pt := prevState[0], prevState[1], prevState[2]
			if pt == currentAns-1 {
				ans[pm][pc][pt] = currentAns
				q.PushBack([]int{pm, pc, pt})
			} else {
				degree[pm][pc][pt]--
				if degree[pm][pc][pt] == 0 {
					ans[pm][pc][pt] = currentAns
					q.PushBack([]int{pm, pc, pt})
				}
			}
		}
	}
	return ans[mouseStart][catStart][0]
}

func getPrevStates(gMouse, gCat [][]int, m, c, t int, ans [][][]int) [][]int {
	pt := t ^ 1
	pre := [][]int{}
	if pt == 1 {
		for _, pc := range gCat[c] {
			if ans[m][pc][1] == 0 {
				pre = append(pre, []int{m, pc, pt})
			}
		}
	} else {
		for _, pm := range gMouse[m] {
			if ans[pm][c][0] == 0 {
				pre = append(pre, []int{pm, c, pt})
			}
		}
	}
	return pre
}

Rust

impl Solution {
    pub fn can_mouse_win(grid: Vec<String>, cat_jump: i32, mouse_jump: i32) -> bool {
        let m = grid.len();
        let n = grid[0].len();

        let grid: Vec<Vec<char>> = grid.iter().map(|s| s.chars().collect()).collect();

        let mut cat_start = 0usize;
        let mut mouse_start = 0usize;
        let mut food = 0usize;

        let dirs = [-1, 0, 1, 0, -1];

        let mut g_mouse = vec![Vec::<usize>::new(); m * n];
        let mut g_cat = vec![Vec::<usize>::new(); m * n];

        for i in 0..m {
            for j in 0..n {
                let c = grid[i][j];
                if c == '#' {
                    continue;
                }

                let v = i * n + j;

                if c == 'C' {
                    cat_start = v;
                } else if c == 'M' {
                    mouse_start = v;
                } else if c == 'F' {
                    food = v;
                }

                for d in 0..4 {
                    let a = dirs[d];
                    let b = dirs[d + 1];

                    for k in 0..=mouse_jump {
                        let x = i as i32 + k * a;
                        let y = j as i32 + k * b;

                        if !(x >= 0
                            && x < m as i32
                            && y >= 0
                            && y < n as i32
                            && grid[x as usize][y as usize] != '#')
                        {
                            break;
                        }

                        g_mouse[v].push((x as usize) * n + y as usize);
                    }

                    for k in 0..=cat_jump {
                        let x = i as i32 + k * a;
                        let y = j as i32 + k * b;

                        if !(x >= 0
                            && x < m as i32
                            && y >= 0
                            && y < n as i32
                            && grid[x as usize][y as usize] != '#')
                        {
                            break;
                        }

                        g_cat[v].push((x as usize) * n + y as usize);
                    }
                }
            }
        }

        use std::collections::VecDeque;

        let n2 = m * n;

        let mut degree = vec![vec![vec![0i32; 2]; n2]; n2];
        let mut ans = vec![vec![vec![0i32; 2]; n2]; n2];

        for i in 0..n2 {
            for j in 0..n2 {
                degree[i][j][0] = g_mouse[i].len() as i32;
                degree[i][j][1] = g_cat[j].len() as i32;
            }
        }

        let mut q = VecDeque::new();

        for i in 0..n2 {
            ans[food][i][1] = 1;
            ans[i][food][0] = 2;
            ans[i][i][1] = 2;
            ans[i][i][0] = 2;

            q.push_back((food, i, 1));
            q.push_back((i, food, 0));
            q.push_back((i, i, 0));
            q.push_back((i, i, 1));
        }

        while let Some((m_pos, c_pos, t)) = q.pop_front() {
            let current_ans = ans[m_pos][c_pos][t];

            let pt = t ^ 1;

            if pt == 1 {
                for &pc in &g_cat[c_pos] {
                    if ans[m_pos][pc][1] != 0 {
                        continue;
                    }

                    if pt as i32 == current_ans - 1 {
                        ans[m_pos][pc][1] = current_ans;
                        q.push_back((m_pos, pc, 1));
                    } else {
                        degree[m_pos][pc][1] -= 1;
                        if degree[m_pos][pc][1] == 0 {
                            ans[m_pos][pc][1] = current_ans;
                            q.push_back((m_pos, pc, 1));
                        }
                    }
                }
            } else {
                for &pm in &g_mouse[m_pos] {
                    if ans[pm][c_pos][0] != 0 {
                        continue;
                    }

                    if pt as i32 == current_ans - 1 {
                        ans[pm][c_pos][0] = current_ans;
                        q.push_back((pm, c_pos, 0));
                    } else {
                        degree[pm][c_pos][0] -= 1;
                        if degree[pm][c_pos][0] == 0 {
                            ans[pm][c_pos][0] = current_ans;
                            q.push_back((pm, c_pos, 0));
                        }
                    }
                }
            }
        }

        ans[mouse_start][cat_start][0] == 1
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Minimax with Memoization	Time Complexity: O(n^4) due to recursive state space exploration up to a depth of 1000 moves potential. Space Complexity: O(n^4) because of memoization of the states, where n is the number of grid cells.
Breadth-First Search with State Tracking	Time Complexity: O(n^4) as we explore potential grid configurations extensively within the move constraint. Space Complexity: O(n^4) because of the queue storage for state exploration.
Topological Sorting	–

Approach

Complexity

Minimax with Memoization

Time Complexity: O(n^4) due to recursive state space exploration up to a depth of 1000 moves potential.

Space Complexity: O(n^4) because of memoization of the states, where n is the number of grid cells.

Breadth-First Search with State Tracking

Time Complexity: O(n^4) as we explore potential grid configurations extensively within the move constraint.

Space Complexity: O(n^4) because of the queue storage for state exploration.

Topological Sorting

–

Complexity analysis

Approach	Time	Space	When to Use
Minimax with Memoization	O((mn)^2 * K)	O((mn)^2 * K)	Best conceptual approach for interviews when modeling adversarial games
BFS with State Tracking (Retrograde Analysis)	O((mn)^2 * K)	O((mn)^2 * K)	Useful for large game graphs where backward propagation avoids deep recursion

Frequently asked questions

Is Cat and Mouse II easy or hard?

Cat and Mouse II is classified as a Hard problem on LeetCode. It requires combining grid traversal, game theory reasoning, dynamic programming over states, and careful handling of cycles or repeated positions.

Cat and Mouse II Python/Java solution

Python implementations usually use DFS with memoization and a state cache keyed by mouse position, cat position, and turn. Java and C++ solutions often implement BFS with state tracking and degree counting to perform retrograde analysis over the game graph.

How to solve Cat and Mouse II in O(n)?

An O(n) solution is not feasible because the game state depends on both mouse and cat positions. The minimum state space is roughly (m*n)^2 with an additional turn dimension. Efficient solutions reduce the search using memoization or BFS-based retrograde analysis over the state graph.

What is the best approach for Cat and Mouse II?

The most common approach is minimax with memoization. Each game state is defined by the mouse position, cat position, and whose turn it is. DFS explores all possible moves while caching results to avoid recomputation. This converts the adversarial game into a dynamic programming problem over states.

Is Cat and Mouse II asked at Google/Amazon/Meta?

Game theory and adversarial search problems like Cat and Mouse II appear in interviews at companies such as Google, Meta, and Amazon. While the exact problem may not appear frequently, the techniques—minimax search, memoization, and graph state modeling—are common interview topics.

What data structure is used in Cat and Mouse II?

The solution relies on grids, graph-style state representations, and memoization tables or DP arrays. DFS recursion with caching or BFS queues are typically used to evaluate game states and propagate winning or losing outcomes.

What is the time complexity of Cat and Mouse II?

The typical solution runs in about O((m*n)^2 * K), where m*n represents grid cells and K is the maximum number of turns considered (often capped near 1000). The state space includes mouse position, cat position, and turn. Memoization or BFS state pruning prevents exponential exploration.

Cat and Mouse II solution and explanation

The problem

Approach overview

Approach 1: Minimax with Memoization

Approach 2: Breadth-First Search with State Tracking

Approach 3: Topological Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Cat and Mouse II solution and explanation

The problem

Approach overview

Approach 1: Minimax with Memoization

Approach 2: Breadth-First Search with State Tracking

Approach 3: Topological Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems