HardRating 2567
913. Cat and Mouse
mathdynamic-programminggraphtopological-sortmemoizationgame-theory
解題說明
Cat and Mouse
題目描述： 在一個無向圖上，貓和老鼠玩遊戲。老鼠在節點 1，貓在節點 2，洞在節點 0。老鼠先走，雙方輪流移動到相鄰節點。老鼠到達洞(0)則老鼠贏，貓抓到老鼠（同一節點）則貓贏，貓不能進入洞(0)。雙方都最優策略下，誰會贏？
解題思路：
- 博弈論 + 拓撲排序式 BFS：狀態定義為 (mouse_pos, cat_pos, turn)，其中 turn 表示輪到誰走。
- 終態：mouse_pos == 0 → 老鼠贏(1)；mouse_pos == cat_pos → 貓贏(2)。
- 反向推理：從已知結果的終態開始，反向推導其他狀態的結果。
- 對於老鼠回合的狀態：如果有任何一步能到達老鼠贏的狀態 → 老鼠贏；如果所有步都導致貓贏 → 貓贏。
- 對於貓回合的狀態：如果有任何一步能到達貓贏的狀態 → 貓贏；如果所有步都導致老鼠贏 → 老鼠贏。
- 無法確定的狀態為平局(0)。
C++ 解法
複雜度分析
時間複雜度：O(n^2 * E) — n 為節點數，E 為邊數。狀態空間 O(n^2)，每個狀態最多處理其鄰居
空間複雜度：O(n^2) — 存儲所有狀態的結果和度數
虛擬碼
1. Define states as (mouse_pos, cat_pos, turn)
2. Initialize degree[m][c][t] = number of moves available
3. Set base cases:
- mouse at hole (pos 0): mouse wins
- mouse at same pos as cat: cat wins
4. BFS from base cases (reverse game search):
a. For each determined state (m, c, t):
b. Find all predecessor states
c. For each predecessor (pm, pc, pt):
- If mover at pt can win with result res: mark and enqueue
- Else decrement degree; if 0: all moves lose, mark losing result
5. Return result[1][2][0] (mouse at 1, cat at 2, mouse's turn)其他解法
-
記憶化搜尋 + 最大步數限制：用 DFS 搜尋所有可能的博弈狀態。為避免無限循環，設置最大深度為 2n（超過視為平局）。時間複雜度 O(n^3)，但實作更直覺。
-
Minimax + Alpha-Beta 剪枝：經典博弈搜尋方法。但因為有平局狀態且圖可能有環，需要額外處理循環檢測，實作較複雜。
延伸思考
- 如果貓的速度是老鼠的兩倍（每回合可以走兩步），結果會怎麼改變？
- 如果有多隻貓或多隻老鼠，問題的複雜度是什麼？
- 如何修改算法以支持加權圖（邊有不同的通過代價）？