HardRating 2849
1728. Cat and Mouse II
arraymathdynamic-programminggraphtopological-sortmemoizationmatrixgame-theory
解題說明
Cat and Mouse II
題目描述：在一個網格上，貓和老鼠輪流移動。老鼠先手，每步可沿上下左右移動 1 到 mouseJump 格；貓每步可移動 1 到 catJump 格。老鼠到達食物位置則老鼠贏，貓到達老鼠位置或食物位置則貓贏。若超過 1000 步未結束則貓贏。判斷老鼠是否能贏。
解題思路：使用記憶化搜索（博弈 DP）。狀態為 (mousePos, catPos, turn)，其中 turn 表示輪到誰移動。老鼠回合選擇任意一步使自己能贏的位置，貓回合選擇任意一步使老鼠輸的位置。用步數限制（上限 128 步足夠，因為網格最多 8x8=64 格）避免無限遞迴。位置用 row * cols + col 壓縮為一維。
C++ 解法
複雜度分析
時間複雜度：O(n^2 × n × 4) — 狀態數為 O(n^2 × 2)（老鼠位置 × 貓位置 × 輪次），每個狀態展開最多 4 個方向各 max(catJump, mouseJump) 步。其中 n = rows × cols <= 64。
空間複雜度：O(n^2) — 記憶化陣列的大小，加上遞迴棧深度 O(n^2)。
虛擬碼
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)
其他解法
拓撲排序（反向分析）：從已知結局狀態出發，使用 BFS 反向推導每個狀態的勝負。類似經典貓鼠遊戲的解法，避免遞迴深度問題，但實作上需要建立完整的狀態轉移圖。
Alpha-Beta 剪枝：在 minimax 搜索中加入 alpha-beta 剪枝，減少不必要的分支探索。適合對局樹較大的情況，但最壞情況下不改善漸進複雜度。
延伸思考
- 若網格更大（例如 20x20），記憶化搜索的空間是否可承受？有什麼優化策略？
- 若貓和老鼠可以斜向移動，狀態空間如何變化？
- 若有多隻貓或多個食物，問題的複雜度如何改變？