猫和老鼠

标签: 图 拓扑排序 记忆化搜索 数学 动态规划 博弈

难度: Hard

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

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

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

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

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

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

  • 如果猫和老鼠出现在同一个节点，猫获胜。
  • 如果老鼠到达洞中，老鼠获胜。
  • 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。

给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

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

示例 1：

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

示例 2：

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

提示：

  • 3 <= graph.length <= 50
  • 1 <= graph[i].length < graph.length
  • 0 <= graph[i][j] < graph.length
  • graph[i][j] != i
  • graph[i] 互不相同
  • 猫和老鼠在游戏中总是可以移动

Submission

运行时间: 237 ms

内存: 17.1 MB

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        f = [[[[0, 0] for _ in range(2)] for _ in range(n)] for _ in range(n)]
        st = []
        for i in range(n):
            for j in range(n):
                for k in range(2):
                    if i == 0 or j == 0:
                        f[i][j][k] = [0, 1]   # 老鼠胜
                        st.append((i, j, k))
                    elif i == j:
                        f[i][j][k] = [0, -1]
                        st.append((i, j, k))
                    else:
                        if k == 0:
                            f[i][j][k][0] = len(graph[i])
                        else:
                            f[i][j][k][0] = len(graph[j])
        while st:
            i, j, k = st.pop()
            if k == 0:   # 猫动，不能走到0
                for x in graph[j]:
                    pre = f[i][x][1]
                    if pre[0]:
                        if f[i][j][k][1] == 1:
                            pre[0] = 0
                            pre[1] = 1
                        else:
                            pre[0] -= 1
                            if pre[0] == 0:
                                pre[0] = 0
                                pre[1] = -1
                        if pre[0] == 0:
                            st.append((i, x, 1))
            else:
                for x in graph[i]:
                    pre = f[x][j][0]
                    if pre[0]:
                        if f[i][j][k][1] == -1:
                            pre[0] = 0
                            pre[1] = -1
                        else:
                            pre[0] -= 1
                            if pre[0] == 0:
                                pre[0] = 0
                                pre[1] = 1
                        if pre[0] == 0:
                            st.append((x, j, 0))
        return f[2][1][1][1] % 3

Explain

这个题解使用了动态规划的思路。定义一个四维数组f[i][j][k]，表示当前猫在i位置，老鼠在j位置，当前移动方是k（0表示猫，1表示老鼠）时的游戏结果。首先初始化一些已知的状态，如老鼠到达0位置（胜利），猫和老鼠在同一位置（猫胜利）等。然后使用一个栈st来进行状态转移，每次弹出一个状态，根据当前移动方更新其他影响的状态，并将新状态加入栈中，直到所有状态都更新完毕。最后返回f[2][1][1][1]，表示初始状态（猫在2，老鼠在1，老鼠先移动）的游戏结果。

时间复杂度: O(n^4)

空间复杂度: O(n^3)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        # 定义状态数组 f[i][j][k]，表示猫在i，老鼠在j，当前移动方为k时的游戏结果
        f = [[[[0, 0] for _ in range(2)] for _ in range(n)] for _ in range(n)]
        st = []
        for i in range(n):
            for j in range(n):
                for k in range(2):
                    if i == 0 or j == 0:
                        f[i][j][k] = [0, 1]   # 老鼠到达0，老鼠胜
                        st.append((i, j, k))
                    elif i == j:
                        f[i][j][k] = [0, -1]  # 猫和老鼠在同一位置，猫胜
                        st.append((i, j, k))
                    else:
                        if k == 0:
                            f[i][j][k][0] = len(graph[i])
                        else:
                            f[i][j][k][0] = len(graph[j])
        while st:
            i, j, k = st.pop()
            if k == 0:   # 猫移动
                for x in graph[j]:
                    if x == 0: # 猫不能移动到0
                        continue
                    pre = f[i][x][1]
                    if pre[0]:
                        if f[i][j][k][1] == 1:
                            pre[0] = 0
                            pre[1] = 1
                        else:
                            pre[0] -= 1
                            if pre[0] == 0:
                                pre[0] = 0
                                pre[1] = -1
                        if pre[0] == 0:
                            st.append((i, x, 1))
            else:  # 老鼠移动 
                for x in graph[i]:
                    pre = f[x][j][0]
                    if pre[0]:
                        if f[i][j][k][1] == -1:
                            pre[0] = 0
                            pre[1] = -1
                        else:
                            pre[0] -= 1
                            if pre[0] == 0:
                                pre[0] = 0
                                pre[1] = 1
                        if pre[0] == 0:
                            st.append((x, j, 0))
        return f[2][1][1][1] % 3

Explore

在状态数组f[i][j][k]中，k的值为0代表当前是猫的移动回合，k的值为1代表当前是老鼠的移动回合。因此，k=0时表示判断猫在i位置，老鼠在j位置时的游戏结果，而k=1时表示判断老鼠在j位置，猫在i位置时的游戏结果。

在这个游戏模型中，每个玩家的决策不仅取决于当前的位置，还受到对手未来动作的影响。因此，动态规划在计算状态时，需要考虑对手的所有可能移动如何影响当前玩家的最终结果。这种方法能够确保无论对手如何响应，都能找到最优的策略。状态转移时，我们需要从对手的可能决策中推断出最不利或最有利的结果，来更新当前状态，从而确保策略的全局最优。

在传统的动态规划中，状态通常是按照某种固定顺序（如递增、递减等）逐步填表或更新的。而使用栈的动态规划则是基于依赖关系动态地进行状态更新。当一个状态改变时，可能会影响其他依赖此状态的多个状态，这些状态会被加入到栈中等待处理。这种方法允许算法灵活地处理那些复杂依赖关系的问题，尤其适用于游戏类问题，在这类问题中，各个状态之间的依赖关系可能非常复杂且难以预测。

这是因为游戏规则通常假设猫和老鼠在同一个位置时，猫能够捕捉到老鼠，因此无论当前是哪个玩家的回合，结果都是猫胜。这种规则反映了游戏的基本目标和机制，即猫的目标是捕捉老鼠，而老鼠的目标是逃到安全的地方。因此，一旦他们处于同一位置，游戏立即以猫的胜利结束。