题目链接：913. 猫和老鼠
动态规划。
几个概念：
- 必胜状态，如果猫的下一步就能赢，那么这个状态就是猫的必胜状态，同时，如果轮到猫走，且猫可以走一步使状态变为必胜状态，那这个状态也是猫的必胜状态；
- 必败状态，如果这个状态是猫的必胜状态，那它即是老鼠的必败状态；
- 必和状态，如果轮到猫走，但无法将状态变为猫的必胜状态，此时如果可以使状态也无法变为老鼠的必胜状态，那么猫可以将其变为必和状态，反之亦然。
记忆化搜索，从初始状态开始，memory[(mouse, cat, turns))] 表示在第 turns 步时，老鼠在 mouse 结点上，猫在 cat 结点上，这个点的状态(取值 0, 1, 2)。递归搜索，直到搜索到终止条件：
- 如果老鼠到了
0结点，那老鼠赢； - 否则，如果老鼠和猫到了同一结点，那猫赢；
- 否则，查找下一步的可能性：
- 如果这个状态能够变为自己的必胜状态，那么本状态即为必胜状态；
- 否则，若本状态可以变为必和状态，那么本状态也是必和状态；
- 否则，本状态就是本方的必败状态。
Note: 如果游戏已经进行了 2n 轮，n 为总的结点数目，还没有结束，那么这个状态就是必和状态。因为此时，除了 0 结点，老鼠已经到达过了所有的剩余结点，猫也到达过了所有的非 0 结点。此时，由于猫和老鼠都是按照最优策略在进行游戏，猫和老鼠都无法获胜。
from typing import List
class Solution:
DRAW = 0
MOUSE_WIN = 1
CAT_WIN = 2
def catMouseGame(self, graph: List[List[int]]) -> int:
n, memory = len(graph), dict()
def get_result(mouse: int, cat: int, turns: int) -> int:
if turns == n * 2:
return self.DRAW
if (mouse, cat, turns) in memory:
return memory.get((mouse, cat, turns))
if mouse == 0:
res = self.MOUSE_WIN
elif cat == mouse:
res = self.CAT_WIN
else:
res = get_next_result(mouse, cat, turns)
memory[(mouse, cat, turns)] = res
return res
def get_next_result(mouse: int, cat: int, turns: int) -> int:
cur_move = mouse if turns % 2 == 0 else cat
default_res = self.MOUSE_WIN if cur_move != mouse else self.CAT_WIN
res = default_res
for next_node in graph[cur_move]:
if cur_move == cat and next_node == 0:
continue
next_mouse = next_node if cur_move == mouse else mouse
next_cat = next_node if cur_move == cat else cat
next_res = get_result(next_mouse, next_cat, turns + 1)
if next_res != default_res:
res = next_res
if res != self.DRAW:
break
return res
return get_result(1, 2, 0)