LeetCode 913: Cat and Mouse

题目链接

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%