Участник:Novitskiy97/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
```