[0913] 猫和老鼠

• GitHub
• http://leetcode.xuezhisd.top/post/c04cbb1d.html
• https://leetcode.com/problems/cat-and-mouse
• https://leetcode-cn.com/problems/cat-and-mouse

题目描述

两个玩家分别扮演猫（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] 包含非零元素。

Related Topics

广度优先搜索

极小化极大

题目解析

• [请一句话描述题目…]

不确定性

方法一：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目