Hard
题目描述
有一个无向图，两名玩家老鼠和猫在图上进行游戏，交替行动。
图的表示如下：graph[a] 是所有节点 b 的列表，使得 ab 是图的一条边。
老鼠从节点 1 开始并首先行动，猫从节点 2 开始并第二个行动，在节点 0 处有一个洞。
在每个玩家的回合中，他们必须沿着图的一条边行进到与他们当前位置相邻的节点。例如，如果老鼠在节点 1，它必须移动到 graph[1] 中的任意节点。
此外，猫不允许移动到洞（节点 0）。
然后，游戏可以通过三种方式结束：
- 如果猫和老鼠占据相同的节点，猫获胜。
- 如果老鼠到达洞，老鼠获胜。
- 如果某个位置重复出现（即玩家处于与之前回合相同的位置，并且轮到同一玩家移动），游戏平局。
给定一个图，假设两个玩家都以最优策略行动，返回：
- 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 <= 501 <= graph[i].length < graph.length0 <= graph[i][j] < graph.lengthgraph[i][j] != igraph[i]是唯一的- 老鼠和猫总能移动
解题思路
这是一个经典的博弈论问题，可以使用拓扑排序结合动态规划来解决。
核心思路：
- 状态表示：使用三维状态
dp[mouse][cat][turn]表示老鼠在位置mouse，猫在位置cat，轮到turn（0表示老鼠，1表示猫）时的游戏结果。 - 结果定义：0表示平局，1表示老鼠胜利，2表示猫胜利。
- 边界条件：
- 老鼠到达洞（位置0）：老鼠胜利
- 猫与老鼠同位置：猫胜利
- 拓扑排序：从已知结果的状态开始，逆向推导其他状态的结果。
- 度数统计：对每个状态计算其可达状态数量，当某个状态的所有可达状态都对当前玩家不利时，该状态对当前玩家也不利。
算法步骤：
- 初始化所有边界状态并加入队列
- 对每个状态计算其可达状态的度数
- 使用拓扑排序，从已确定的状态开始更新其父状态
- 如果某个状态的所有子状态都对当前玩家不利，则该状态也不利
- 如果某个状态存在对当前玩家有利的子状态，则该状态有利
最终返回初始状态 dp[1][2][0] 的结果。
代码实现
class Solution {
public:
int catMouseGame(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
vector<vector<vector<int>>> degree(n, vector<vector<int>>(n, vector<int>(2, 0)));
// 计算每个状态的度数
for (int m = 0; m < n; m++) {
for (int c = 0; c < n; c++) {
degree[m][c][0] = graph[m].size();
degree[m][c][1] = graph[c].size();
// 猫不能进入洞
for (int node : graph[c]) {
if (node == 0) {
degree[m][c][1]--;
break;
}
}
}
}
queue<vector<int>> q;
// 初始化边界状态
for (int i = 0; i < n; i++) {
for (int t = 0; t < 2; t++) {
dp[0][i][t] = 1; // 老鼠在洞里，老鼠胜利
q.push({0, i, t, 1});
if (i > 0) {
dp[i][i][t] = 2; // 猫抓到老鼠，猫胜利
q.push({i, i, t, 2});
}
}
}
while (!q.empty()) {
auto cur = q.front();
q.pop();
int mouse = cur[0], cat = cur[1], turn = cur[2], result = cur[3];
if (turn == 0) { // 当前是老鼠回合，查看上一轮猫的状态
for (int prevCat : graph[cat]) {
if (prevCat == 0) continue; // 猫不能进洞
if (dp[mouse][prevCat][1] != 0) continue;
if (result == 2) { // 猫胜利，猫会选择这个状态
dp[mouse][prevCat][1] = 2;
q.push({mouse, prevCat, 1, 2});
} else { // 老鼠胜利，猫的度数减1
degree[mouse][prevCat][1]--;
if (degree[mouse][prevCat][1] == 0) { // 猫的所有选择都对猫不利
dp[mouse][prevCat][1] = 1;
q.push({mouse, prevCat, 1, 1});
}
}
}
} else { // 当前是猫回合，查看上一轮老鼠的状态
for (int prevMouse : graph[mouse]) {
if (dp[prevMouse][cat][0] != 0) continue;
if (result == 1) { // 老鼠胜利，老鼠会选择这个状态
dp[prevMouse][cat][0] = 1;
q.push({prevMouse, cat, 0, 1});
} else { // 猫胜利，老鼠的度数减1
degree[prevMouse][cat][0]--;
if (degree[prevMouse][cat][0] == 0) { // 老鼠的所有选择都对老鼠不利
dp[prevMouse][cat][0] = 2;
q.push({prevMouse, cat, 0, 2});
}
}
}
}
}
return dp[1][2][0];
}
};
class Solution:
def catMouseGame(self, graph: List[List[int]]) -> int:
n = len(graph)
dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]
degree = [[[0] * 2 for _ in range(n)] for _ in range(n)]
# 计算每个状态的度数
for m in range(n):
for c in range(n):
degree[m][c][0] = len(graph[m])
degree[m][c][1] = len(graph[c])
# 猫不能进入洞
if 0 in graph[c]:
degree[m][c][1] -= 1
queue = deque()
# 初始化边界状态
for i in range(n):
for t in range(2):
dp[0][i][t] = 1 # 老鼠在洞里，老鼠胜利
queue.append((0, i, t, 1))
if i > 0:
dp[i][i][t] = 2 # 猫抓到老鼠，猫胜利
queue.append((i, i, t, 2))
while queue:
mouse, cat, turn, result = queue.popleft()
if turn == 0: # 当前是老鼠回合，查看上一轮猫的状态
for prev_cat in graph[cat]:
if prev_cat == 0: # 猫不能进洞
continue
if dp[mouse][prev_cat][1] != 0:
continue
if result == 2: # 猫胜利，猫会选择这个状态
dp[mouse][prev_cat][1] = 2
queue.append((mouse, prev_cat, 1, 2))
else: # 老鼠胜利，猫的度数减1
degree[mouse][prev_cat][1] -= 1
if degree[mouse][prev_cat][1] == 0: # 猫的所有选择都对猫不利
dp[mouse][prev_cat][1] = 1
queue.append((mouse, prev_cat, 1, 1))
else: # 当前是猫回合，查看上一轮老鼠的状态
for prev_mouse in graph[mouse]:
if dp[prev_mouse][cat][0] != 0:
continue
if result == 1: # 老鼠胜利，老鼠会选择这个状态
dp[prev_mouse][cat][0] = 1
queue.append((prev_mouse, cat, 0, 1))
else: # 猫胜利，老鼠的度数减1
degree[prev_mouse][cat][0] -= 1
if degree[prev_mouse][cat][0] == 0: # 老鼠的所有选择都对老鼠不利
dp[prev_mouse][cat][0] = 2
queue.append((prev_mouse, cat, 0, 2))
return dp[1][2][0]
public class Solution {
public int CatMouseGame(int[][] graph) {
int n = graph.Length;
int[,,] dp = new int[n, n, 2];
int[,,] degree = new int[n, n, 2];
// 计算每个状态的度数
for (int m = 0; m < n; m++) {
for (int c = 0; c < n; c++) {
degree[m, c, 0] = graph[m].Length;
degree[m, c, 1] = graph[c].Length;
// 猫不能进入洞
foreach (int node in graph[c]) {
if (node == 0) {
degree[m, c, 1]--;
break;
}
}
}
}
Queue<int[]> queue = new Queue<int[]>();
// 初始化边界状态
for (int i = 0; i < n; i++) {
for (int t = 0; t < 2; t++) {
dp[0, i, t] = 1; // 老鼠在洞里，老鼠胜利
queue.Enqueue(new int[] {0, i, t, 1});
if (i > 0) {
dp[i, i, t] = 2; // 猫抓到老鼠，猫胜利
queue.Enqueue(new int[] {i, i, t, 2});
}
}
}
while (queue.Count > 0) {
int[] cur = queue.Dequeue();
int mouse = cur[0], cat = cur[1], turn = cur[2], result = cur[3];
if (turn == 0) { // 当前是老鼠回合，查看上一轮猫的状态
foreach (int prevCat in graph[cat]) {
if (prevCat == 0) continue; // 猫不能进洞
if (dp[mouse, prevCat, 1] != 0) continue;
if (result == 2) { // 猫胜利，猫会选择这个状态
dp[mouse, prevCat, 1] = 2;
queue.Enqueue(new int[] {mouse, prevCat, 1, 2});
} else { // 老鼠胜利，猫的度数减1
degree[mouse, prevCat, 1]--;
if (degree[mouse, prevCat, 1] == 0) { // 猫的所有选择都对猫不利
dp[mouse, prevCat, 1] = 1;
queue.Enqueue(new int[] {mouse, prevCat, 1, 1});
}
}
}
} else { // 当前是猫回合，查看上一轮老鼠的状态
foreach (int prevMouse in graph[mouse]) {
if (dp[prevMouse, cat, 0] != 0) continue;
if (result == 1) { // 老鼠胜利，老鼠会选择这个状态
dp[prevMouse, cat, 0] = 1;
queue.Enqueue(new int[] {prevMouse, cat, 0, 1});
} else { // 猫胜利，老鼠的度数减1
degree[prevMouse, cat, 0]--;
if (degree[prevMouse, cat, 0] == 0) { // 老鼠的所有选择都对老鼠不利
dp[prevMouse, cat, 0] = 2;
queue.Enqueue(new int[] {prevMouse, cat, 0, 2});
}
}
}
}
}
return dp[1, 2, 0];
}
}
var catMouseGame = function(graph) {
const n = graph.length;
const DRAW = 0, MOUSE = 1, CAT = 2;
// color[node][cat][turn] = outcome
const color = Array(n).fill().map(() =>
Array(n).fill().map(() => Array(2).fill(DRAW))
);
// degree[node][cat][turn] = number of possible moves
const degree = Array(n).fill().map(() =>
Array(n).fill().map(() => Array(2).fill(0))
);
// Initialize degrees
for (let m = 0; m < n; m++) {
for (let c = 0; c < n; c++) {
degree[m][c][0] = graph[m].length;
degree[m][c][1] = graph[c].length;
for (let node of graph[c]) {
if (node === 0) {
degree[m][c][1]--;
break;
}
}
}
}
const queue = [];
// Initialize terminal positions
for (let c = 0; c < n; c++) {
for (let t = 0; t < 2; t++) {
color[0][c][t] = MOUSE;
queue.push([0, c, t, MOUSE]);
if (c > 0) {
color[c][c][t] = CAT;
queue.push([c, c, t, CAT]);
}
}
}
// Propagate results backwards
while (queue.length > 0) {
const [mouse, cat, turn, result] = queue.shift();
if (turn === 0) { // Mouse's turn, so previous turn was cat's
for (let prevCat of graph[cat]) {
if (prevCat === 0) continue;
if (color[mouse][prevCat][1] !== DRAW) continue;
if (result === CAT) {
color[mouse][prevCat][1] = CAT;
queue.push([mouse, prevCat, 1, CAT]);
} else {
degree[mouse][prevCat][1]--;
if (degree[mouse][prevCat][1] === 0) {
color[mouse][prevCat][1] = MOUSE;
queue.push([mouse, prevCat, 1, MOUSE]);
}
}
}
} else { // Cat's turn, so previous turn was mouse's
for (let prevMouse of graph[mouse]) {
if (color[prevMouse][cat][0] !== DRAW) continue;
if (result === MOUSE) {
color[prevMouse][cat][0] = MOUSE;
queue.push([prevMouse, cat, 0, MOUSE]);
} else {
degree[prevMouse][cat][0]--;
if (degree[prevMouse][cat][0] === 0) {
color[prevMouse][cat][0] = CAT;
queue.push([prevMouse, cat, 0, CAT]);
}
}
}
}
}
return color[1][2][0];
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n³)，其中 n 是图中节点数。需要处理 O(n²) 个状态，每个状态最多被访问常数次。 |
| 空间复杂度 | O(n²)，用于存储 dp 数组和 degree 数组。 |
相关题目
- . Cat and Mouse II (Hard)