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;
        }
    }

};