跳转至

LeetCode: 913. 猫和老鼠

1、题目描述

两个玩家分别扮演猫(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] 包含非零元素。

2、解题思路

首先,用元组的方式表示老鼠和猫的位置,

(老鼠的位置,猫的位置,当前移动的是老鼠还是猫,胜利者)

老鼠位置:i
猫的位置:j
当前移动的是老鼠还是猫:
    老鼠:1
    猫:2

胜利者:
  平局:0
    老鼠:1
    猫 :2

我们能够确认,当老鼠处于位置0的时候,胜利者是老鼠

(0,*,1 or 2, 1)

当猫和老鼠处在同一个位置的时候,并且位置不为0,胜利者为猫

(x,x,1 or 2, 2)  x!=0

因此,以这些确定的状态作为出发点,根据路径的连通性,判断能够编程当前状态的上一个状态的胜利者,也就是负状态状态

例1:
    假如当前状态为:
    (0,3,1,1)
        老鼠在位置0,猫在位置3,本次应该老鼠移动,胜利者为老鼠
那什么状态能够变成当前的状态呢?
        因为当前是老鼠在移动,因此,前一次的状态肯定是猫在移动,这时候,我们需要判断找到与猫的位置联通的线路,假设是2,4,5,因此前一个状态可能是:
        (0,2,2)
        (0,4,2)
        (0,5,2)
        上面这几种状态是猫在移动,但是并不能直接判定是老鼠还是猫赢
        因为猫很聪明,每一次抓的时候指向最佳路径,所以想要确定猫是输的,必须后面的路径全部都是老鼠赢,才能判定是老鼠胜利

例2:
    假如当前状态为:
    (0,3,2,1)
  老鼠在位置0,猫在位置3,本次应该猫移动,胜利者为老鼠
  所以,想要变成当前状态,就需要判断与位置0有几条通路,假设值2,5
    (2,3,1)
        (5,3,1)
    因为老鼠是想要胜利的,所以会选择最优线路,因此,上面两种状态就都是老鼠会赢,因为是老鼠先走,下一步就是老鼠回到了0处
from collections import deque, defaultdict


class Solution:
    def catMouseGame(self, graph: [[int]]) -> int:
        length = len(graph)
        DRAW, MOUSE, CAT = 0, 1, 2

        def parent(mouse_pos, cat_pos, tune):
            """
            得到上一步的路径
            :param i: 老鼠位置
            :param j: 猫的位置
            :param t: 当前是老鼠还是猫再走
                    1:老鼠
                    2:猫
            :return:
            """
            if tune == 1:
                for cat in graph[cat_pos]:
                    if cat:
                        yield (mouse_pos, cat, 3 - t)
            else:
                for mouse in graph[mouse_pos]:
                    yield (mouse, cat_pos, 3 - t)

        # 存放结果集
        result = defaultdict(int)

        # 表示当前状态可走路径有多少条

        branch = {}

        for m in range(length):
            for c in range(length):
                branch[m, c, 1] = len(graph[m])
                # 猫不能回到0
                branch[m, c, 2] = len(graph[c]) - (1 if 0 in graph[c] else 0)

        d = deque([])

        # 将确定胜利的放入队列中
        for i in range(length):
            for t in range(1, 3):
                result[(0, i, t)] = MOUSE
                d.append((0, i, t, MOUSE))
                if i > 0:
                    result[(i, i, t)] = CAT
                    d.append((i, i, t, CAT))
        while d:
            if result[1, 2, 1] != DRAW:
                break
            m, c, t, s = d.popleft()

            for m1, c1, t1 in parent(m, c, t):

                if result[m1, c1, t1] == DRAW:
                    if t1 == s:
                        # 如果上一步操作在移动的与本次的胜利者是一样的,那么上一次的状态与本次是一样的
                        result[(m1, c1, t1)] = s
                        d.append((m1, c1, t1, s))
                    else:
                        # 如果上一次移动的结果与本次胜利者不同,那么就需要判断是不是所有的路径都是不同的胜利者
                        branch[m1, c1, t1] -= 1
                        if branch[m1, c1, t1] == 0:
                            # 表示所有的路径胜利者都是对方
                            result[m1, c1, t1] = 3 - t1
                            d.append((m1, c1, t1, 3 - t1))

        return result[(1, 2, 1)]