# 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。

```
示例：
- 输入：[[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] 包含非零元素。
```

方法：

1. 使用一个向量表示当前的状态f(t,x,y),其中，t表示下一步该谁走，当t=0时默认是老鼠先走。x表示老鼠此时所在节点，y表示猫所在节点，状态初始化为-1。
2. 当x==y时表示猫抓到老鼠，返回2；x==0时表示老鼠进洞，返回1；
3. 然后判断当前该谁走，通过递归调用的方法得到最终状态。
4. 如果是老鼠先走，则判断老鼠的下一步可以走哪里，如果能走到0处，即得到状态1，则老鼠获胜；使用flag表示当前下一步可走的位置，如果下一步的状态永远是2，则注定老鼠失败，猫获胜，如果有一个不是，则flag为flase。
5. 如果猫先走，也是同样的方法，看下一步是否能够遇到老鼠，如果能打到状态1，则猫获胜；使用flag表示当前下一步可走位置，如果下一步状态永远是1，则注定猫失败，老鼠获胜，如果有一个不是，则flag为flase。此前还需要判断下一个状态不能跑到0节点，因为猫无法进洞。
6. 最后调用该函数，传如初始状态，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;
        }
    }

};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/913.cat_and_mouse.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.