0913. Cat and Mouse¶
题目信息¶
- 题号:
0913
- 难度:
Hard
- 主题:
图、轮流博弈、胜负与平局
- 原题:
- 重点:
老鼠从节点 1、猫从节点 2 出发且老鼠先走;猫不能进入洞 0,返回值
1、2、0分别表示老鼠胜、猫胜和平局
题目重述¶
给定无向图的邻接表 graph。老鼠初始位于节点 1,猫初始位于节点 2,洞位于节点 0。双方轮流沿一条相邻边移动,老鼠先行动;猫在任何时候都不能移动到节点 0。
若老鼠到达节点 0,老鼠获胜;若猫与老鼠位于同一节点,猫获胜。双方都选择使自身结果最优的行动。若某个包含双方位置与当前行动者的状态再次出现,则游戏进入循环并判为平局。
请返回 1 表示老鼠获胜,返回 2 表示猫获胜,返回 0 表示平局。3 <= graph.length <= 50,图中没有自环或重复边。
自建示例¶
老鼠第一步无处避开猫:
输入:graph = [[2],[2],[0,1]]
输出:2
解释:老鼠位于节点 1,唯一能走到节点 2,而猫初始就在节点 2。老鼠移动后两者重合,因此猫获胜。
老鼠可以第一步进入洞:
输入:graph = [[1],[0,2],[1]]
输出:1
解释:老鼠从节点 1 直接移动到洞 0,立即获胜;猫所在的节点 2 来不及行动。