0913. Cat and Mouse

题目信息

题号:

0913

难度:

Hard

主题:

图、轮流博弈、胜负与平局

原题:

LeetCode 0913

重点:

老鼠从节点 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 来不及行动。