Cat and Mouse II - Video Solutions
Cat mouse II leetcode, asked in Amazon interview π±π
Cat and Mouse II - Video Solution
Watch 9 video solutions for Cat and Mouse II, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Amritanjali has 2,255 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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'ingrid.
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, mouseJumpare 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.lengthcols = grid[i].length1 <= rows, cols <= 8grid[i][j]consist only of characters'C','M','F','.', and'#'.- There is only one of each character
'C','M', and'F'ingrid. 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.
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 |