Skip to content

Latest commit

 

History

History
177 lines (103 loc) · 6.77 KB

0913._Cat_and_Mouse.md

File metadata and controls

177 lines (103 loc) · 6.77 KB

913. Cat and Mouse

难度: Hard

刷题内容

原题连接

内容描述

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

Mouse starts at node 1 and goes first, Cat starts at node 2 and goes second, and there is a Hole at node 0.

During each player's turn, they must travel along one edge of the graph that meets where they are.  For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)

Then, the game can end in 3 ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (ie. the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.
Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.

 

Example 1:

Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Explanation:
4---3---1
|   |
2---5
 \ /
  0
 

Note:

3 <= graph.length <= 50
It is guaranteed that graph[1] is non-empty.
It is guaranteed that graph[2] contains a non-zero element.

解题方案

思路 1 - 时间复杂度: O(N^3)- 空间复杂度: O(N^2)******

之前写的版本不能AC了，因为有人新增了test case，也说明之前的解法是错的

于是看了solution，写了下面的版本

对于某一个点(mouse, cat, turn)

  • turn为1,mouse走; turn为2,cat走
  • mouse为0，说明mouse到了点0，mouse胜
  • mouse和cat相等，说明cat抓到了mouse，cat胜

然后对于点(mouse, cat, turn)，我们先看看哪些点能够到达它，这些能够到达它的点就是它的parent

  • 如果parent的turn是1说明在parent点轮到mouse走，
    • 如果parent的某一个孩子点(mouse, cat, turn)的状态是mouse必胜的话，说明parent点本身状态也是mouse必胜，因为mouse走一步可以到达mouse必胜的点
    • 如果parent的所有孩子点的状态都是cat的话，说明此时从parent点无论怎么样都是cat胜，说明parent点本身状态就是cat必胜
  • 如果parent的turn是2说明在parent点轮到cat走，
    • 如果parent的某一个孩子点(mouse, cat, turn)的状态是cat必胜的话，说明parent点本身状态也是cat必胜，因为cat走一步可以到达cat必胜的点
    • 如果parent的所有孩子点的状态都是mouse的话，说明此时从parent点无论怎么样都是mouse胜，说明parent点本身状态就是mouse必胜

刚才也说明了初始状态我们可以知道mouse为0的点都是mouse胜，cat和mouse相等的点都是cat胜，我们把这些确定了胜利状态的点放到一个queue中， 然后对于这些确认了状态的点point，我们挨个找他们的parent然后根据parent的turn和point的状态是否相等可以对parent进行判断

  • 如果parent的turn和点point的状态相等，说明parent的状态可以确定与点point的状态相等，那么parent的状态确定了我们也要将其放到queue中去
  • 如果parent的turn和点point的状态不相等，说明parent下一步轮到mouse/cat走，但却到达了一个cat/mouse必胜的点，此时我们知道我们还要维护每一个点 的孩子节点数量（注意初始化取孩子数量的时候cat不能为0，因为题目里面说cat不能到0），因为每次到了这个情况里面我们需要把孩子数量减去1，当孩子数量减到0的时候我们就知道了parent的所有孩子的状态都和parent的turn不相等， 这说明什么呢？
    • 说明只要parent下一步是mouse走，cat必胜；
    • 只要parent下一步是cat走，mouse必胜 那么这又说明什么呢，说明parent的状态也算定下来了，然后我们又可以把parent放到queue中去

最终所有点的状态都知道了，我们直接return点(1, 2, 1)，因为mouse开始在1，cat开始在2，第一步是mouse走

class Solution(object):
    def catMouseGame(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        N = len(graph)
        # 从哪个点可以到达点(mouse, cat, turn)，即点(mouse, cat, turn)的parents
        def parents(mouse, cat, turn): # turn为1,mouse走; turn为2,cat走
            if turn == 2:
                for mouse2 in graph[mouse]:
                    yield mouse2, cat, 3-turn
            else:
                for cat2 in graph[cat]:
                    if cat2:
                        yield mouse, cat2, 3-turn

        DRAW, MOUSE, CAT = 0, 1, 2
        state = collections.defaultdict(int)

        degree = {} # degree[node] : the number of neutral children of this node
        for mouse in range(N):
            for cat in range(N):
                degree[mouse, cat, 1] = len(graph[mouse])
                degree[mouse, cat, 2] = len(graph[cat]) - (0 in graph[cat]) # cat不能到0

        queue = collections.deque([]) # 所有确定了必胜状态的点
        for i in range(N):
            for turn in range(1, 3):
                state[0, i, turn] = MOUSE # mouse到达0, mouse胜
                queue.append((0, i, turn, MOUSE)) # 确定了必胜状态，放到queue中
                if i > 0:
                    state[i, i, turn] = CAT # cat和mouse相等，cat胜
                    queue.append((i, i, turn, CAT)) # 确定了必胜状态，放到queue中

        while queue:
            mouse, cat, turn, victory = queue.popleft()
            for mouse2, cat2, turn2 in parents(mouse, cat, turn):
                if state[mouse2, cat2, turn2] == DRAW: # parent状态是平局
                    if turn2 == victory: # parent的下一步轮到mouse/cat走，到达了一个mouse/cat必胜的点
                        state[mouse2, cat2, turn2] = victory # 那么parent肯定也是mouse/cat必胜
                        queue.append((mouse2, cat2, turn2, victory)) # 确定了必胜状态，放回queue中
                    else: # parent的下一步轮到mouse/cat走，到达了一个cat/mouse必胜的点
                        degree[mouse2, cat2, turn2] -= 1 # parent的其中一个孩子与其走的结果正好相反，例如mouse走，走到一个cat必胜点
                        if degree[mouse2, cat2, turn2] == 0: # parent所有孩子都与其走的结果正好相反
                            state[mouse2, cat2, turn2] = 3 - turn2 # 例如mouse走，cat必胜，那么这个点也是cat必胜
                            queue.append((mouse2, cat2, turn2, 3 - turn2)) # # 确定了必胜状态，放回queue中

        return state[1, 2, 1]