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 剪枝:經典博弈搜尋方法。但因為有平局狀態且圖可能有環,需要額外處理循環檢測,實作較複雜。
延伸思考
- 如果貓的速度是老鼠的兩倍(每回合可以走兩步),結果會怎麼改變?
- 如果有多隻貓或多隻老鼠,問題的複雜度是什麼?
- 如何修改算法以支持加權圖(邊有不同的通過代價)?