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``,图中没有自环或重复边。 自建示例 -------- 老鼠第一步无处避开猫: .. code-block:: text 输入:graph = [[2],[2],[0,1]] 输出:2 解释:老鼠位于节点 1,唯一能走到节点 2,而猫初始就在节点 2。老鼠移动后两者重合,因此猫获胜。 老鼠可以第一步进入洞: .. code-block:: text 输入:graph = [[1],[0,2],[1]] 输出:1 解释:老鼠从节点 1 直接移动到洞 0,立即获胜;猫所在的节点 2 来不及行动。