Cat and Mouse

A game is played on an undirected graph by two players, Mouse and Cat, who alternate turns. The graph is given as an adjacency list. The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0. Players must travel along one edge of the graph during their turn. The cat cannot travel to the hole (node 0). The game ends if:

1. The Cat occupies the same node as the Mouse (Cat wins).
2. The Mouse reaches the Hole (Mouse wins).
3. A position is repeated (Draw).

Given a graph, and assuming both players play optimally, return 1 if the mouse wins, 2 if the cat wins, or 0 if the game is a draw.

Example:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0

Input: graph = [[1,3],[0],[3],[0,2]] Output: 1

Constraints:

• 3 <= graph.length <= 50
• 1 <= graph[i].length < graph.length
• 0 <= graph[i][j] < graph.length
• graph[i][j] != i
• graph[i] is unique.
• The mouse and the cat can always move.

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        DRAW = 0
        MOUSE = 1
        CAT = 2
        
        # Initialize the state of each node
        # state[mouse, cat, turns] = result
        # result = 0 (draw), 1 (mouse wins), 2 (cat wins)
        state = [[[0] * (2 * n) for _ in range(n)] for _ in range(n)]
        
        # Initialize the degree of each node
        degree = [[[len(graph[i]) for i in range(n)] for _ in range(n)] for _ in range(n)]
        
        # Initialize the queue with the winning states
        queue = []
        for j in range(1, n):
            state[0][j][0] = MOUSE # Mouse wins if it reaches the hole
            state[0][j][1] = MOUSE
            state[1][j][0] = MOUSE # Mouse wins if it starts at the hole
            state[1][j][1] = MOUSE
            state[j][j][0] = CAT   # Cat wins if it catches the mouse
            state[j][j][1] = CAT
            queue.append((0, j, 0))
            queue.append((0, j, 1))
            queue.append((1, j, 0))
            queue.append((j, j, 0))
            queue.append((j, j, 1))

        
        # Start the BFS
        while queue:
            i, j, turn = queue.pop(0)
            result = state[i][j][turn]
            
            # Propagate the result to the previous states
            # If it's mouse's turn, the previous state is cat's turn
            # If it's cat's turn, the previous state is mouse's turn
            if turn == 0: # Mouse's turn
                for prev_j in graph[j]: # Previous cat position
                    if prev_j == 0: continue # Cat cannot go to the hole
                    if state[i][prev_j][1] != DRAW: continue # Already visited
                    
                    # If all possible moves for the cat leads to the mouse winning, then the cat loses
                    cat_win = True
                    for next_i in graph[i]:
                        if state[next_i][prev_j][0] == DRAW:
                            cat_win = False
                            break
                    if cat_win:
                        state[i][prev_j][1] = MOUSE
                        queue.append((i, prev_j, 1))
                    else:
                        degree[i][prev_j][1] -= 1
                        if degree[i][prev_j][1] == 0:
                            state[i][prev_j][1] = DRAW
                            queue.append((i, prev_j, 1))
            else: # Cat's turn
                for prev_i in graph[i]: # Previous mouse position
                    if state[prev_i][j][0] != DRAW: continue # Already visited
                    
                    state[prev_i][j][0] = CAT
                    queue.append((prev_i, j, 0))
        
        return state[1][2][0]

Explanation:

The problem can be solved using dynamic programming and breadth-first search (BFS). The key idea is to start from the end states (where the mouse wins or the cat wins) and propagate the results to the previous states.

1. State Definition: state[mouse, cat, turn] represents the state of the game, where mouse is the position of the mouse, cat is the position of the cat, and turn indicates whose turn it is (0 for mouse, 1 for cat). The value of the state is 0 for draw, 1 for mouse wins, and 2 for cat wins.
2. Initialization: Initialize the states where the mouse wins (reaches the hole) or the cat wins (catches the mouse). Add these states to the queue.
3. BFS: Use BFS to propagate the results from the end states to the previous states. For each state in the queue, check the possible previous states. If all possible moves for the current player lead to the other player winning, then the current player loses.
4. Return Value: Return the state of the game where the mouse starts at node 1, the cat starts at node 2, and it is the mouse's turn.

Big(O) Run-time Analysis:

The time complexity is O(N^3), where N is the number of nodes in the graph. This is because the state space is O(N^3) (N possible mouse positions, N possible cat positions, and 2N turns), and the BFS algorithm visits each state at most once.

Big(O) Space Usage Analysis:

The space complexity is O(N^3), where N is the number of nodes in the graph. This is because the state space is O(N^3) (N possible mouse positions, N possible cat positions, and 2N turns), and the state array stores the result of each state.