#913
Cat and Mouse
master · 1865 · lc hard +32 · verified · 34.8% accepted · 1,013 likes · top 12%
Description
An undirected graph is given as graph where graph[a] lists all neighbors of node a. Mouse starts at node 1 and moves first; Cat starts at node 2. On each turn the active player moves to any adjacent node — Cat may not enter node 0 (the hole). Mouse wins if it reaches node 0; Cat wins if it occupies the same node as Mouse; otherwise the game is a draw.
With both players playing optimally, return 1 if Mouse wins, 2 if Cat wins, or 0 for a draw.
Example 1:
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Example 2:
Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1
Code
1
2
3