LeetCode 913: Cat and Mouse

发表于 | | 阅读次数:
字数统计: 1.1k | 阅读时长 ≈ 4

题目链接

https://leetcode.com/problems/cat-and-mouse/

题意

两个玩家分别扮演猫（Cat）和老鼠（Mouse）在无向图上进行游戏，他们轮流行动。

该图按下述规则给出：graph[a] 是所有结点 b 的列表，使得 ab 是图的一条边。

老鼠从结点 1 开始并率先出发，猫从结点 2 开始且随后出发，在结点 0 处有一个洞。

在每个玩家的回合中，他们必须沿着与他们所在位置相吻合的图的一条边移动。例如，如果老鼠位于结点 1，那么它只能移动到 graph[1] 中的（任何）结点去。

此外，猫无法移动到洞（结点 0）里。

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

  • 如果猫和老鼠占据相同的结点，猫获胜。
  • 如果老鼠躲入洞里，老鼠获胜。
  • 如果某一位置重复出现（即，玩家们的位置和移动顺序都与上一个回合相同），游戏平局。

给定 graph，并假设两个玩家都以最佳状态参与游戏，如果老鼠获胜，则返回 1；如果猫获胜，则返回 2；如果平局，则返回 0。

题目类型

博弈 图论

题目分析

大概是遇到的最难的LeetCode的题了。看了张慕辉的题解后照搬着写了一遍才感觉有点理解。

首先定义color[mPos][cPos][turn]表示老鼠走到mPos，猫走到cPos时候的必胜状态，1表示老鼠赢，2表示猫赢(turn也是同样数字定义)

注意到其中有一些点的胜负状态是确定的，规则如下：

  • 当mPos = 0，老鼠胜
  • 当mPos = cPos，猫胜

因此我们可以由这些确定的状态出发，往前反推，去推理其他状态下的博弈情况。把所有已经确定状态还没有反推的点压入队列。回推时一旦确定一个状态的color就压入队列继续反推，思想有点类似于拓扑排序。

反推的时候，因为猫鼠都是最佳状态，说明绝对不会主动走进败局，且有胜利机会则必走。

因此，当上一步轮到MOUSE走，当前的color是MOUSE时可以直接染色上一步的状态。

当前的color是CAT时，老鼠除非是走投无路一定不会走过来，因此记录一下上一状态的出度，遇见一次就出度减一，当出度为零时说明所有该状态的下招都是猫胜，上一状态也只能是猫胜了，记录为猫胜压入队列。

如果有状态到最后都没被染色，说明这个状态是平局，因为没有被必败也没有必胜，因此只有平了。这个特性推几个例子可以有一些理解。

时间复杂度

$O(N ^ {3})$

源代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
struct node {
    int cPos, mPos;
    int turn;
    node (int m, int c, int t): cPos(c), mPos(m), turn(t) {}
};
class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        int n = graph.size();
        const int MOUSE = 1, CAT = 2;
        int i, j;
        int color[202][202][3];
        int outDegree[202][202][3];
        queue<node>q;
        memset(color, 0, sizeof(color));
        memset(outDegree, 0, sizeof(outDegree));
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (j == 0)
                    continue;
                if (i == 0) {
                    color[i][j][CAT] = color[i][j][MOUSE] = MOUSE;
                    q.emplace(i, j, MOUSE);
                    q.emplace(i, j, CAT);
                    continue;
                }
                if (i == j) {
                    color[i][j][CAT] = color[i][j][MOUSE] = CAT;
                    q.emplace(i, j, MOUSE);
                    q.emplace(i, j, CAT);
                    continue;
                }
                outDegree[i][j][MOUSE] = graph[i].size();
                for (int x: graph[j])
                    if (x)
                        outDegree[i][j][CAT]++;
            }
        }
        while (!q.empty()) {
            node cur = q.front(); q.pop();
            int mPos = cur.mPos, cPos = cur.cPos, turn = cur.turn;
            if (color[mPos][cPos][turn] == 0)
                continue;
            if (turn == MOUSE) {
                for (int x: graph[cPos]) {
                    if (x == 0 || color[mPos][x][CAT]) continue;
                    if (color[mPos][cPos][turn] == CAT) {
                        color[mPos][x][CAT] = CAT;
                        q.emplace(mPos, x, CAT);
                    } else {
                       outDegree[mPos][x][CAT]--;
                       if (outDegree[mPos][x][CAT] == 0) {
                           color[mPos][x][CAT] = MOUSE;
                           q.emplace(mPos, x, CAT);
                       }
                    }
                }
            }
            else {
                for (int x: graph[mPos]) {
                    if (color[x][cPos][MOUSE]) continue;
                    if (color[mPos][cPos][turn] == MOUSE) {
                        color[x][cPos][MOUSE] = MOUSE;
                        q.emplace(x, cPos, MOUSE);
                    } else {
                        outDegree[x][cPos][MOUSE]--;
                        if (outDegree[x][cPos][MOUSE] == 0) {
                            color[x][cPos][MOUSE] = CAT;
                            q.emplace(x, cPos, MOUSE);
                        }
                    }
                }
            }
        }
        return color[1][2][MOUSE];
    }
};
0%