Участник:Novitskiy97/Cat and Mouse

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/cat-and-mouse/

Python 3

 
class Solution:
    def catMouseGame(self, graph):
        N = len(graph)
        state = (1, 2, 0) 
        Mouse, Cat, Draw = 1, 2, 0
        hashmap = defaultdict(int)
        q = deque()
        q2 = deque()
        for n in range(1, N):
            hashmap[n,n,0] = Cat
            hashmap[n,n,1] = Cat
            hashmap[0,n,0] = Mouse
            hashmap[0,n,1] = Mouse
            q.append((0, n, 0))
            q.append((0, n, 1))
            q2.append((n, n, 0))
            q2.append((n, n, 1))
 
        def nei(vertex, ismouse):
            return tuple(v for v in graph[vertex] if ismouse or v != 0)
 
        indeg = defaultdict(int)
        for x in range(N):
            for y in range(1, N):
                t = 1
                indeg[x, y, t] = len(nei(y, False))
 
        indeg2 = defaultdict(int)
        for x in range(N):
            for y in range(1, N):
                t = 0
                indeg2[x, y, t] = len(nei(x, True))
 
        while q:
            qsize = len(q)
            for _ in range(qsize):
                x, y, t = q.popleft()
 
                if t == 1:
                    for x_next in nei(x, True):
                        node = (x_next, y, 0)
                        if hashmap[node] == 0:
                            hashmap[node] = Mouse
                            q.append(node)
                            if state == node:
                                return Mouse
 
                elif t == 0:
                    for y_next in nei(y, False):
                        node = (x, y_next, 1)
                        indeg[node] -= 1
                        if indeg[node] == 0 and hashmap[node] == Draw:
                            hashmap[node] = Mouse
                            q.append(node)
                            if state == node:
                                return Mouse
 
        q = q2
        indeg = indeg2
        while q:
            qsize = len(q)
            for _ in range(qsize):
                x, y, t = q.popleft()
 
                if t == 0:
                    for y_next in nei(y, False):
                        node = (x, y_next, 1)
                        if hashmap[node] == 0:
                            hashmap[node] = Cat
                            q.append(node) 
                            if state == node:
                                return Cat
 
                elif t == 1:
                    for x_next in nei(x, True):
                        node = (x_next, y, 0)
                        indeg[node] -= 1
                        if indeg[node] == 0 and hashmap[node] == Draw:
                            hashmap[node] = Cat
                            q.append(node)
                            if state == node:
                                return Cat
 
        return Draw