Problem statement

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

Solution 1

Consider state: (position of mouse, position of can, number of move). We can create new graph with vertexes being these positions and steps being moves. We can notice, that it is enough to make 2n steps, and if we make more, we have a draw. There are O(n^3) positions and O(n^2m) possible edges in new graph, where m is number of edges in original graph. It can be shown, that:

  1. For mouse move, that is where time is divisible by 2: if we have any neighbor equal to 1, we return 1, if we have all neighbors equal to 2, we return 2. In other case, we return 0: draw
  2. Similar logic for cat, but we also need to restrict it not to move to hole.

Complexity

Final time complexity is O(n^2m), space complexity is O(n^3).

Code

class Solution:
    def catMouseGame(self, graph):
        n = len(graph)
        
        @lru_cache(None)
        def dfs(M, K, time):
            if time >= 2*n: return 0
            if K == M: return 2
            if M == 0: return 1
            
            if time % 2 == 0: # mouse turn
                if any(dfs(neib, K, time+1) == 1 for neib in graph[M]): return 1
                if all(dfs(neib, K, time+1) == 2 for neib in graph[M]): return 2
            else: # cat turn
                if any(dfs(M, neib, time+1) == 2 for neib in graph[K] if neib != 0): return 2
                if all(dfs(M, neib, time+1) == 1 for neib in graph[K] if neib != 0): return 1
            return 0
            
        return dfs(1, 2, 0)

Solution 2

There is also O(mn) complexity solution, using the idea of topological sort. The idea is similar to previous approach: we create 2n^2 possible states and then we need to traverse graph: first we put all positions we know answer for: winning positions for cat and mouse. Then we traverse inverse edges and if color is not defined yet, we check neighbors: if we have the same color, we color it; in opposite case we decrease degree of node and if degree is zero, that is all is visited, we can color it to opposite color.

Complexity

Time is O(mn), space is O(n^2).

Code

#### borrowed code
class Solution(object):
    def catMouseGame(self, graph):
        N = len(graph)
        adj_rev = defaultdict(list)
        degree = Counter()
        
        #new graph construction
        for i in range(N):
            for j in range(N):
                for neib in graph[i]: # turn = 0 - mouse
                    adj_rev[(neib, j, 2)].append((i, j, 1))
                    degree[(i, j, 1)] += 1
                for neib in graph[j]:
                    if neib != 0:  #cat can not go to hole
                        adj_rev[(i, neib, 1)].append((i, j, 2))
                        degree[(i, j, 2)] += 1

        DRAW, MOUSE, CAT = 0, 1, 2
        color = defaultdict(int)

        queue = deque([])
        for i in range(N):
            for t in range(1, 3):
                color[0, i, t] = MOUSE
                queue.append((0, i, t, MOUSE))
                if i > 0:
                    color[i, i, t] = CAT
                    queue.append((i, i, t, CAT))

        while queue:
            M, C, t, c = queue.popleft()
            for M2, C2, t2 in adj_rev[(M, C, t)]:
                if color[M2, C2, t2] is DRAW:
                    if t2 == c: # winning move
                        color[M2, C2, t2] = c
                        queue.append((M2, C2, t2, c))
                    else:
                        degree[M2, C2, t2] -= 1
                        if degree[M2, C2, t2] == 0:
                            color[M2, C2, t2] = 3 - t2
                            queue.append((M2, C2, t2, 3 - t2))

        return color[1, 2, 1]