# 913. Cat and Mouse 猫和老鼠

@TOC

## # 题目描述

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:

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

## # 题目大意

1. Cat和Mouse进入同一结点，则Cat胜利
2. Mouse进入0结点，则Mouse胜利
3. Cat和Mouse的位置和回合发生了重复，则平局

## # 解题方法

``````class Solution(object):
def catMouseGame(self, graph):
"""
:type graph: List[List[int]]
:rtype: int
"""
N = len(graph)
MOUSE, CAT = 1, 2
# mouse, cat, turn
color = [[[0] * 3 for i in range(N)] for j in range(N)]
q = collections.deque()
for i in range(1, N):
for t in range(1, 3):
color[0][i][t] = 1
q.append((0, i, t))
color[i][i][t] = 2
q.append((i, i, t))
while q:
curStatus = q.popleft()
cat, mouse, turn = curStatus
for preStatus in self.findAllPrevStatus(graph, curStatus):
preCat, preMouse, preTurn = preStatus
if color[preCat][preMouse][preTurn] != 0:
continue
if color[cat][mouse][turn] == 3 - turn:
color[preCat][preMouse][preTurn] = preTurn
q.append(preStatus)
elif self.allNeighboursWin(color, graph, preStatus):
color[preCat][preMouse][preTurn] = 3 - preTurn
q.append(preStatus)
return color[1][2][1]

def findAllPrevStatus(self, graph, curStatus):
ret = []
mouse, cat, turn = curStatus
if turn == 1:
for preCat in graph[cat]:
if preCat == 0:
continue
ret.append((mouse, preCat, 2))
else:
for preMouse in graph[mouse]:
ret.append((preMouse, cat, 1))
return ret

def allNeighboursWin(self, color, graph, status):
mouse, cat, turn = status
if turn == 1:
for nextMouse in graph[mouse]:
if color[nextMouse][cat][2] != 2:
return False
elif turn == 2:
for nextCat in graph[cat]:
if nextCat == 0:
continue
if color[mouse][nextCat][1] != 1:
return False
return True
``````

## # 参考资料

https://zhanghuimeng.github.io/post/leetcode-913-cat-and-mouse/ https://github.com/wisdompeak/LeetCode/tree/master/BFS/913.Cat-and-Mouse

## # 日期

2018 年 10 月 24 日 —— 程序员节被严重炒作了啊