913. Cat and Mouse

解題說明

C++ 解法

複雜度分析

虛擬碼

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)

其他解法

延伸思考