【Leetcode-2022.1.4】913. 猫和老鼠

77 阅读 0 评论 51 点赞

我是靠谱客的博主俏皮睫毛膏，这篇文章主要介绍【Leetcode-2022.1.4】913. 猫和老鼠，现在分享给大家，希望可以做个参考。

猫和老鼠
题目：两位玩家分别扮演猫和老鼠，在一张无向图上进行游戏，两人轮流行动。图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。在每个玩家的行动中，他们必须沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。此外，猫无法移动到洞中（节点 0）。然后，游戏在出现以下三种情形之一时结束：
1.如果猫和老鼠出现在同一个节点，猫获胜。
2.如果老鼠到达洞中，老鼠获胜。
3.如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都以最佳状态参与游戏：
如果老鼠获胜，则返回 1；如果猫获胜，则返回 2；如果平局，则返回 0 。
输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0
方法一：记忆化搜索(又是CV的一天)

dp[mouse][cat][k] 表示从老鼠位于节点mouse、猫位于节点cat、游戏已经进行了k轮的状态开始，猫和老鼠都按照最优策略的情况下的游戏结果。
最优策略的选择顺序：胜–平--输

复制代码

class Solution {
static final int DRAW = 0;
static final int MOUSE = 1;
static final int CAT = 2;
int n;
int[][] graph;
int[][][] dp;
public int catMouseGame(int[][] graph) {
n = graph.length;
this.graph = graph;
this.dp = new int[n][n][n * 2];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
Arrays.fill(dp[i][j],-1);
}
}
return getResult(1,2,0);
}
//获取比赛结果（鼠的坐标，猫的坐标，第几轮）
public int getResult(int mouse, int cat, int k){
if(k == n * 2) return DRAW;
if(dp[mouse][cat][k] == -1){
if(mouse == 0) dp[mouse][cat][k] = MOUSE;
else if(mouse == cat) dp[mouse][cat][k] = CAT;
else getNext(mouse,cat,k);
}
return dp[mouse][cat][k];
}
//选择策略
public void getNext(int mouse, int cat, int k){
int cur = k % 2 == 0 ? mouse : cat;//根据轮数判断当前移动的角色
int bestResult = cur == mouse ? MOUSE : CAT;//最优结果
//选择最优的策略：胜--平--输
int curResult = bestResult;//当前结果
int result = cur == mouse ?
CAT : MOUSE;//默认最差结果
for(int i : graph[cur]){//下一步的位置
if(cur == cat && i == 0) continue;
curResult = cur == mouse ? getResult(i, cat, k + 1) : getResult(mouse, i, k + 1) ;
//如果得到最优结果可以提前退出循环，得到平局和最差结果需要继续循环
if(curResult == bestResult){
result = bestResult;
break;
}else if(curResult == DRAW){
result = DRAW;
}
}
dp[mouse][cat][k] = result;
}
}

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
class Solution {
static final int DRAW = 0;
static final int MOUSE = 1;
static final int CAT = 2;
int n;
int[][] graph;
int[][][] dp;
public int catMouseGame(int[][] graph) {
n = graph.length;
this.graph = graph;
this.dp = new int[n][n][n * 2];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
Arrays.fill(dp[i][j],-1);
}
}
return getResult(1,2,0);
}
//获取比赛结果（鼠的坐标，猫的坐标，第几轮）
public int getResult(int mouse, int cat, int k){
if(k == n * 2) return DRAW;
if(dp[mouse][cat][k] == -1){
if(mouse == 0) dp[mouse][cat][k] = MOUSE;
else if(mouse == cat) dp[mouse][cat][k] = CAT;
else getNext(mouse,cat,k);
}
return dp[mouse][cat][k];
}
//选择策略
public void getNext(int mouse, int cat, int k){
int cur = k % 2 == 0 ? mouse : cat;//根据轮数判断当前移动的角色
int bestResult = cur == mouse ? MOUSE : CAT;//最优结果
//选择最优的策略：胜--平--输
int curResult = bestResult;//当前结果
int result = cur == mouse ?
CAT : MOUSE;//默认最差结果
for(int i : graph[cur]){//下一步的位置
if(cur == cat && i == 0) continue;
curResult = cur == mouse ? getResult(i, cat, k + 1) : getResult(mouse, i, k + 1) ;
//如果得到最优结果可以提前退出循环，得到平局和最差结果需要继续循环
if(curResult == bestResult){
result = bestResult;
break;
}else if(curResult == DRAW){
result = DRAW;
}
}
dp[mouse][cat][k] = result;
}
}