913.Cat and Mouse
913.Cat and Mouse
两个玩家分别扮演猫(Cat)和老鼠(Mouse)在无向图上进行游戏,他们轮流行动。 该图按下述规则给出:graph[a] 是所有结点 b 的列表,使得 ab 是图的一条边。 老鼠从结点 1 开始并率先出发,猫从结点 2 开始且随后出发,在结点 0 处有一个洞。 在每个玩家的回合中,他们必须沿着与他们所在位置相吻合的图的一条边移动。例如,如果老鼠位于结点 1,那么它只能移动到 graph[1] 中的(任何)结点去。 此外,猫无法移动到洞(结点 0)里。 然后,游戏在出现以下三种情形之一时结束: 如果猫和老鼠占据相同的结点,猫获胜。 如果老鼠躲入洞里,老鼠获胜。 如果某一位置重复出现(即,玩家们的位置和移动顺序都与上一个回合相同),游戏平局。 给定 graph,并假设两个玩家都以最佳状态参与游戏,如果老鼠获胜,则返回 1;如果猫获胜,则返回 2;如果平局,则返回 0。
1
示例:
2
- 输入:[[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
3
- 输出:0
4
- 解释:
Copied!
4---3---1 | | 2---5 \ / 0
1
- 提示:
2
3
3 <= graph.length <= 200
4
保证 graph[1] 非空。
5
保证 graph[2] 包含非零元素。
Copied!
方法:
  1. 1.
    使用一个向量表示当前的状态f(t,x,y),其中,t表示下一步该谁走,当t=0时默认是老鼠先走。x表示老鼠此时所在节点,y表示猫所在节点,状态初始化为-1。
  2. 2.
    当x==y时表示猫抓到老鼠,返回2;x==0时表示老鼠进洞,返回1;
  3. 3.
    然后判断当前该谁走,通过递归调用的方法得到最终状态。
  4. 4.
    如果是老鼠先走,则判断老鼠的下一步可以走哪里,如果能走到0处,即得到状态1,则老鼠获胜;使用flag表示当前下一步可走的位置,如果下一步的状态永远是2,则注定老鼠失败,猫获胜,如果有一个不是,则flag为flase。
  5. 5.
    如果猫先走,也是同样的方法,看下一步是否能够遇到老鼠,如果能打到状态1,则猫获胜;使用flag表示当前下一步可走位置,如果下一步状态永远是1,则注定猫失败,老鼠获胜,如果有一个不是,则flag为flase。此前还需要判断下一个状态不能跑到0节点,因为猫无法进洞。
  6. 6.
    最后调用该函数,传如初始状态,f(0,1,2)得到最后结果。
1
class Solution {
2
public:
3
vector<vector<vector<int>>>f;
4
int catMouseGame(vector<vector<int>>& graph) {
5
int size=graph.size();
6
f = vector<vector<vector<int>>>(size*2, vector<vector<int>>(size, vector<int>(size,-1)));
7
return result(graph,0,1,2);
8
}
9
private:
10
int result(const vector<vector<int>>& graph, int t,int x,int y)
11
{
12
if(t == graph.size() *2)
13
return 0;
14
if(x == y)
15
return f[t][x][y]=2;
16
if(x == 0)
17
return f[t][x][y]=1;
18
if(f[t][x][y] !=-1)
19
return f[t][x][y];
20
21
int who = t % 2;
22
bool flag;
23
if(!who)
24
{
25
flag=true;
26
for(int i=0;i<graph[x].size();i++)
27
{
28
int nx= result(graph,t+1,graph[x][i],y);
29
if(nx == 1)
30
return f[t][x][y]=1;
31
if(nx !=2)
32
flag=false;
33
}
34
if (flag)
35
return f[t][x][y]=2;
36
else
37
return f[t][x][y]=0;
38
}
39
else
40
{
41
flag = true;
42
for(int i=0;i<graph[y].size();i++)
43
{
44
if(graph[y][i] ==0) continue;
45
int ny = result(graph,t+1,x,graph[y][i]);
46
if(ny==2)
47
return f[t][x][y]=2;
48
if(ny!=1)
49
flag = false;
50
}
51
if(flag)
52
return f[t][x][y]=1;
53
else
54
return f[t][x][y]=0;
55
}
56
}
57
58
};
Copied!
Copy link