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

};

Last updated