913. 猫和老鼠 - 力扣（LeetCode） (leetcode-cn.com)
题目
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。
题意
在一个无向图中，进猫捉老鼠的游戏。
如果猫和老鼠位于同一位置，则猫赢。
如果老鼠走到节点0，则老鼠赢。
如果某一位置重复出现，则平局。此时应该是猫和老鼠都出现在了重复的位置，才是平局，否则只是单纯的一方出现在重复的位置，那么实则另一方还是有可能会获胜，因为他还有没有走完的位置，还有可能性。
思路
记忆化搜索或者说动态规划
博弈问题，猫和老鼠都足够聪明，那么每一轮，只要当前轮的玩家（猫或者老鼠）在走的时候存在着一种可能性使它获胜，那么此轮玩家一定会走向让自己获胜的那个节点，否则会走向平局的节点，如果没有能平局的点，最后则会走向让自己输的节点。
因此平局的可能性可以表示为，当轮数i大于2*n（n表示总共节点数），可以理解为此时猫和老鼠都走过了n个节点，那么下一轮的节点必定都是重复的。
那么其实就可以用搜索达到上面的过程，对于每一轮，可以使用搜索穷尽子问题的所有状态达到上述的结果。
但是单纯的搜索会超时，因此需要记忆化
令dp[i][j][k]表示第i轮，老鼠在编号为j的节点，猫在编号为k的节点，表示此轮已经得到的是猫赢或者老鼠赢，或者平局。
代码
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
|
#include "algorithm"
#include "vector"
#include "string"
using namespace std;
class Solution {
public:
int dp[100][100][100];
int catMouseGame(vector<vector<int>> &graph) {
for (int i = 0; i < 100; i++)
for(int j = 0; j < 100; j++)
for(int k = 0; k < 100; k++)
dp[k][i][j] = -1;
return dfs(1, 2, graph, 0);
}
int dfs(int curMouse, int curCat, vector<vector<int>> &graph, int st) {
if (dp[st][curCat][curMouse] != -1) return dp[st][curCat][curMouse];
if (st > 2 * graph.size()) return 0;
if (curMouse == 0) return 1;
if (curMouse == curCat) return 2;
if (st % 2 == 0) {
int k = 2;
for (auto &x: graph[curMouse]) {
int t = dfs(x, curCat, graph, st + 1);
if (t == 1) {
dp[st][curCat][curMouse] = 1;
return 1;
}
else if (t == 0) k = 0;
}dp[st][curCat][curMouse] = k;
return k;
} else {
int k = 1;
for (auto &x: graph[curCat])
if (x) {
int t = dfs(curMouse, x, graph, st + 1);
if (t == 2) {
dp[st][curMouse][curCat] = 2;
return 2;
}
else if (t == 0) k = 0;
}dp[st][curCat][curMouse] = k;
return k;
}
}
};
|