猫和老鼠

913. 猫和老鼠 (Hard)

两个玩家分别扮演猫(Cat)和老鼠(Mouse)在无向图上进行游戏,他们轮流行动。

该图按下述规则给出:graph[a] 是所有结点 b 的列表,使得 ab 是图的一条边。

老鼠从结点 1 开始并率先出发,猫从结点 2 开始且随后出发,在结点 0 处有一个洞。

在每个玩家的回合中,他们必须沿着与他们所在位置相吻合的图的一条边移动。例如,如果老鼠位于结点 1,那么它只能移动到 graph[1] 中的(任何)结点去。

此外,猫无法移动到洞(结点 0)里。

然后,游戏在出现以下三种情形之一时结束:

  • 如果猫和老鼠占据相同的结点,猫获胜。
  • 如果老鼠躲入洞里,老鼠获胜。
  • 如果某一位置重复出现(即,玩家们的位置和移动顺序都与上一个回合相同),游戏平局。

给定 graph,并假设两个玩家都以最佳状态参与游戏,如果老鼠获胜,则返回 1;如果猫获胜,则返回 2;如果平局,则返回 0

 

示例:

输入:[[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出:0
解释:
4---3---1
|   |
2---5
 \ /
  0

 

提示:

  1. 3 <= graph.length <= 200
  2. 保证 graph[1] 非空。
  3. 保证 graph[2] 包含非零元素。

相关话题

[广度优先搜索] [极小化极大]


解法