This problem is solved by modeling the grid as a graph and tracking all possible game states with dynamic programming. By computing indegrees for each state and applying topological ordering, you can systematically determine winning and losing states. GhostInterview guides you to propagate outcomes backward from trivial states and efficiently check if the mouse can win before the cat reaches it, avoiding brute-force state explosion.
Problem Statement
In Cat and Mouse II, you are given a grid representing a game environment with walls, floors, a cat, a mouse, and food. The mouse and cat take turns moving, with both able to jump up to mouseJump and catJump cells respectively, in four directions, but cannot move through walls. The mouse wins by reaching the food first, and the cat wins by catching the mouse before that.
Your task is to determine whether the mouse can guarantee a win, given the grid configuration and jump limits. Each move changes the state of the game, and the solution requires considering all reachable positions, capturing cycles, and applying game theory logic to propagate winning and losing states across the graph efficiently.
Examples
Example 1
Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
Output: true
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 details omitted.
Example 3
Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
Output: false
Example details omitted.
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
Solution Approach
Model game states as a graph
Represent each possible configuration of mouse and cat positions as a node in a graph. Track whose turn it is and which moves are allowed based on jump limits. Compute indegree for each node to prepare for backward propagation.
Apply topological ordering and DP
Use a queue to process all trivial terminal states first (mouse at food or cat catches mouse). Propagate winning and losing states backward using indegrees, updating parent nodes when all child states are determined.
Memoization to prune repeated states
Store results of visited states to avoid recomputation. Since the grid and jump constraints are small, memoization combined with topological ordering ensures all states are evaluated efficiently and prevents cycles from causing infinite loops.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time and space complexity depend on the number of possible states, which is rows * cols for both cat and mouse times 2 for turn tracking. Using memoization and topological ordering reduces repeated computation and avoids exploring all permutations explicitly.
What Interviewers Usually Probe
- Expecting graph modeling for positions and moves
- Looking for topological sort with indegree to propagate outcomes
- Checking for awareness of cycles and terminal state propagation
Common Pitfalls or Variants
Common pitfalls
- Ignoring the turn when modeling states leads to incorrect results
- Failing to account for jump limits can create invalid moves
- Not using memoization may cause TLE due to state explosion
Follow-up variants
- Change jump distances for cat and mouse and analyze win guarantees
- Use rectangular grids larger than 8x8 to test DP scalability
- Introduce multiple cats or mice to evaluate generalized topological propagation
How GhostInterview Helps
- GhostInterview generates all reachable states and computes indegrees for backward propagation automatically
- It highlights cycles and terminal conditions to ensure no state is missed
- Provides an efficient DP approach with memoization to quickly determine if mouse can win
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy for Cat and Mouse II?
Model each mouse and cat position as a node, compute indegrees, and apply topological ordering to determine winning states.
How does topological sorting help in this problem?
It propagates outcomes from known terminal states backward to other states, ensuring each state's result is computed only once.
Why memoization is crucial for Cat and Mouse II?
Memoization prevents recalculating repeated states, avoiding time limits exceeded due to combinatorial explosion of positions.
Can this approach handle larger grids or multiple jumps?
Yes, the graph and DP approach scales with jump constraints, but grid size beyond 8x8 may increase computation significantly.
Which pattern does this problem primarily demonstrate?
Graph indegree plus topological ordering pattern, combining game theory with DP to systematically resolve winning and losing states.
Need direct help with Cat and Mouse II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Cat and Mouse II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Number of Increasing Paths in a Grid by turning cell comparisons into a DAG and counting paths with topological DP.
Open problem page#913 Cat and MouseDetermine the outcome of a two-player Cat and Mouse game on a graph using topological ordering and memoized dynamic programming.
Open problem page#329 Longest Increasing Path in a MatrixFind the length of the longest increasing path in a matrix with given movement constraints using graph techniques.
Open problem page