1728. Cat and Mouse II

解題說明

C++ 解法

複雜度分析

虛擬碼

1. Parse grid to find Cat, Mouse, Food positions
2. Define state (mousePos, catPos, turn)
3. solve(mpos, cpos, turn, steps):
   a. Base cases: steps >= 128 -> cat wins; mpos == cpos -> cat wins; cpos == food -> cat wins; mpos == food -> mouse wins
   b. Check memo
   c. If mouse's turn: try all moves (4 dirs, 0..mouseJump steps), return true if any move leads to mouse win
   d. If cat's turn: try all moves (4 dirs, 0..catJump steps), return false (mouse loses) if any move leads to cat win
   e. Store result in memo and return
4. Return solve(mouse0, cat0, 0, 0)

其他解法

延伸思考