猫和老鼠
难度:
标签:
题目描述
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
- 如果猫和老鼠出现在同一个节点，猫获胜。
- 如果老鼠到达洞中，老鼠获胜。
- 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
- 如果老鼠获胜，则返回
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]互不相同- 猫和老鼠在游戏中总是可以移动
代码结果
运行时间: 237 ms, 内存: 17.1 MB
/*
思路：
使用Java Stream API来简化一些操作，尤其是数组遍历和状态更新。
*/
import java.util.Arrays;
public class CatAndMouseStream {
public int catMouseGame(int[][] graph) {
int n = graph.length;
int[][][] dp = new int[n][n][2 * n];
for (int[][] layer : dp) {
for (int[] row : layer) {
Arrays.fill(row, -1);
}
}
return helper(graph, dp, 1, 2, 0);
}
private int helper(int[][] graph, int[][][] dp, int mouse, int cat, int turns) {
if (turns == 2 * graph.length) return 0;
if (mouse == 0) return 1;
if (mouse == cat) return 2;
if (dp[mouse][cat][turns] != -1) return dp[mouse][cat][turns];
if (turns % 2 == 0) {
boolean mouseWin = Arrays.stream(graph[mouse])
.map(next -> helper(graph, dp, next, cat, turns + 1))
.anyMatch(res -> res == 1);
boolean catWin = Arrays.stream(graph[mouse])
.map(next -> helper(graph, dp, next, cat, turns + 1))
.allMatch(res -> res == 2);
dp[mouse][cat][turns] = mouseWin ? 1 : (catWin ? 2 : 0);
} else {
boolean mouseWin = Arrays.stream(graph[cat])
.filter(next -> next != 0)
.map(next -> helper(graph, dp, mouse, next, turns + 1))
.allMatch(res -> res == 1);
boolean catWin = Arrays.stream(graph[cat])
.filter(next -> next != 0)
.map(next -> helper(graph, dp, mouse, next, turns + 1))
.anyMatch(res -> res == 2);
dp[mouse][cat][turns] = catWin ? 2 : (mouseWin ? 1 : 0);
}
return dp[mouse][cat][turns];
}
}
解释
方法:
这个题解使用了动态规划的思路。定义一个四维数组f[i][j][k]，表示当前猫在i位置，老鼠在j位置，当前移动方是k（0表示猫，1表示老鼠）时的游戏结果。首先初始化一些已知的状态，如老鼠到达0位置（胜利），猫和老鼠在同一位置（猫胜利）等。然后使用一个栈st来进行状态转移，每次弹出一个状态，根据当前移动方更新其他影响的状态，并将新状态加入栈中，直到所有状态都更新完毕。最后返回f[2][1][1][1]，表示初始状态（猫在2，老鼠在1，老鼠先移动）的游戏结果。
时间复杂度:
O(n^4)
空间复杂度:
O(n^3)
代码细节讲解
🦆
题解中提到的状态数组f[i][j][k]中的k表示当前移动方，它有两个值0和1。这两个值具体代表猫和老鼠中的哪个？
▷🦆
在动态规划的实现中，为什么状态转移时考虑的是对手的移动影响当前结果，而不是当前玩家的移动直接决定结果？
▷🦆
题解中的状态转移逻辑使用了一个栈来更新状态，这种`栈`的使用与传统的动态规划有何不同？
▷🦆
题解中初始化状态时，为什么当猫和老鼠在同一个位置时，直接判断为猫胜利，即使这是老鼠的回合？
▷