【每日一题】LeetCode 913.猫和老鼠（hard题）

题目

两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

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

如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。

示例

输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0

代码

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        dic={}
        n=len(graph)
        def dp(cat, mouse, cnt):
            if (cat, mouse, cnt) in dic:
                return dic[(cat, mouse, cnt)]
            if cnt>2*n:
                dic[(cat, mouse, cnt)]=0
                return 0
            flag=False
            if cnt%2==0:
                for nx in graph[mouse]:
                    if nx==cat:
                        continue
                    if nx==0:
                        dic[(cat, mouse, cnt)]=1
                        return 1
                    if dp(cat,nx,cnt+1)==1:
                        dic[(cat,mouse,cnt)]=1
                        return 1
                    elif dp(cat, nx, cnt+1)==0:
                        flag=True
                if flag:
                    dic[(cat, mouse, cnt)]=0
                    return 0
                dic[(cat, mouse, cnt)]=2
                return 2
            else:
                for nx in graph[cat]:
                    if nx==mouse:
                        dic[(cat, mouse, cnt)]=2
                        return 2
                    if nx==0:
                        continue
                    if dp(nx, mouse, cnt+1)==0:
                        flag=True
                    elif dp(nx, mouse, cnt+1)==2:
                        dic[(cat, mouse, cnt)]=2
                        return 2
                if flag:
                    dic[(cat, mouse, cnt)]=0
                    return 0
                dic[(cat,mouse,cnt)]=1
                return 1
        return dp(2,1,0)