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