LC 913. 猫和老鼠

题目描述

这是 LeetCode 上的 913. 猫和老鼠 ，难度为 困难。

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

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

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

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。

例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

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

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

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

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

示例 1：

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

输出：0

示例 2：

1
2
3
输入：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] 互不相同
  • 猫和老鼠在游戏中总是移动

动态规划

数据范围只有 $50$，使得本题的难度大大降低。

定义 $f[k][i][j]$ 为当前进行了 $k$ 步，老鼠所在位置为 $i$，猫所在的位置为 $j$ 时，最终的获胜情况（$0$ 为平局，$1$ 和 $2$ 分别代表老鼠和猫获胜），起始我们让所有的 $f[k][i][j] = -1$（为无效值），最终答案为 $f[0][1][2]$。

不失一般性的考虑 $f[i][j][k]$ 该如何转移，根据题意，将当前所在位置 $i$ 和 $j$ 结合「游戏结束，判定游戏」的规则来分情况讨论：

  • 若 $i = 0$，说明老鼠位于洞中，老鼠获胜，此时有 $f[k][i][j] = 1$；
  • 若 $i = j$，说明两者为与同一位置，猫获胜，此时有 $f[k][i][j] = 2$；
  • 考虑如何定义平局，即 $f[k][i][j] = 0$ 的情况？

我们最多有 $n$ 个位置，因此 $(i, j)$ 位置对组合数最多为 $n^2$ 种，然后 $k$ 其实代表的是老鼠先手还是猫先手，共有 $2$ 种可能，因此状态数量数据有明确上界为 $2 * n^2$。

所以我们可以设定 $k$ 的上界为 $2 n^2$（抽屉原理，走超过 $2 n^2$ 步，必然会有相同的局面出现过至少两次），但是这样的计算量为 $2 50^2 50 50 = 1.25 10^7$，有 TLE 风险，转移过程增加剪枝，可以过。

而更小的 $k$ 值需要证明：在最优策略中，相同局面（状态）成环的最大长度的最小值为 $k$。

题目规定轮流移动，且只能按照 $graph$ 中存在的边进行移动。

  1. 如果当前 $k$ 为偶数（该回合老鼠移动），此时所能转移所有点为 $f[k + 1][ne][j]$，其中 $ne$ 为 $i$ 所能到达的点。由于采用的是最优移动策略，因此 $f[k][i][j]$ 会优先往 $f[k + 1][ne][j] = 1$ 的点移动（自身获胜），否则往 $f[k + 1][ne][j] = 0$ 的点移动（平局），再否则才是往 $f[k + 1][ne][j] = 2$ 的点移动（对方获胜）；

  2. 同理，如果当前 $k$ 为奇数（该回合猫移动），此时所能转移所有点为 $f[k + 1][i][ne]$，其中 $ne$ 为 $j$ 所能到达的点。由于采用的是最优移动策略，因此 $f[k][i][j]$ 会优先往 $f[k + 1][i][ne] = 2$ 的点移动（自身获胜），否则往 $f[k + 1][i][ne] = 0$ 的点移动（平局），再否则才是往 $f[k + 1][i][ne] = 1$ 的点移动（对方获胜）。

使用该转移优先级进行递推即可，为了方便我们使用「记忆化搜索」的方式来实现动态规划。

注意，该优先级转移其实存在「贪心」决策，但证明这样的决策会使得「最坏情况最好」是相对容易的，而证明存在更小的 $k$ 值才是本题难点。

一些细节：由于本身就要对动规数组进行无效值的初始化，为避免每个样例都 new 大数组，我们使用 static 来修饰大数组，可以有效减少一点时间（不使用 static 的话，N 只能取到 $51$）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    static int N = 55;
    static int[][][] f = new int[2 * N * N][N][N];
    int[][] g;
    int n;
    public int catMouseGame(int[][] graph) {
        g = graph;
        n = g.length;
        for (int k = 0; k < 2 * n * n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    f[k][i][j] = -1;
                }
            }
        }
        return dfs(0, 1, 2);
    }
    // 0:draw / 1:mouse / 2:cat
    int dfs(int k, int a, int b) {
        int ans = f[k][a][b];
        if (a == 0) ans = 1;
        else if (a == b) ans = 2;
        else if (k >= 2 * n * n) ans = 0;
        else if (ans == -1) {
            if (k % 2 == 0) { // mouse
                boolean win = false, draw = false;
                for (int ne : g[a]) {
                    int t = dfs(k + 1, ne, b);
                    if (t == 1) win = true;
                    else if (t == 0) draw = true;
                    if (win) break;
                }
                if (win) ans = 1;
                else if (draw) ans = 0;
                else ans = 2;
            } else { // cat
                boolean win = false, draw = false;
                for (int ne : g[b]) {
                    if (ne == 0) continue;
                    int t = dfs(k + 1, a, ne);
                    if (t == 2) win = true;
                    else if (t == 0) draw = true;
                    if (win) break;
                }
                if (win) ans = 2;
                else if (draw) ans = 0;
                else ans = 1;
            }
        }
        f[k][a][b] = ans;
        return ans;
    }
}

  • 时间复杂度：状态的数量级为 $n^4$，可以确保每个状态只会被计算一次。复杂度为 $O(n^4)$
  • 空间复杂度：$O(n^4)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.913 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。