Cat and Mouse II - Video Solutions

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.