LeetCode Solutions Blog

Cat and Mouse II

Difficulty: Hard

Problem Description

A game is played by a cat and a mouse named Cat and Mouse. The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food. Mouse moves first, then they take turns to move. The game can end in four ways: if Cat occupies the same position as Mouse, if Cat reaches the food first, if Mouse reaches the food first, or if Mouse cannot get to the food within 1000 turns.

Key Insights

Mouse has the first move advantage, which can influence the game outcome.
The game is played on a grid with walls and floors, making navigation complex.
The maximum jump lengths for Cat and Mouse add strategic depth to their movements.
The game can be analyzed using game theory, where optimal moves can be computed recursively.
A breadth-first search (BFS) or depth-first search (DFS) approach can be used to explore possible moves and outcomes.

Space and Time Complexity

Time Complexity: O(4^(NM)), where N is the number of rows and M is the number of columns, due to the branching factor from possible moves. Space Complexity: O(NM), for the storage of visited states and recursion stack depth.

Solution

To determine if the Mouse can win, we can use a recursive approach with memoization. We will track the positions of the Cat, Mouse, and the food on the grid. The algorithm will evaluate all possible moves for both players, considering the maximum jump lengths. If the Mouse reaches the food first or can evade the Cat indefinitely, it returns true; otherwise, it returns false. The key data structures used are a grid to represent the environment and a memoization table to store already computed states to avoid redundant calculations.

Code Solutions

def catMouseGame(grid, catJump, mouseJump):
    rows, cols = len(grid), len(grid[0])
    mouse, cat, food = None, None, None

    # Locate Mouse, Cat, and Food
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 'M':
                mouse = (r, c)
            elif grid[r][c] == 'C':
                cat = (r, c)
            elif grid[r][c] == 'F':
                food = (r, c)

    # Memoization dictionary
    memo = {}

    def canMouseWin(mousePos, catPos, turn):
        if mousePos == food:  # Mouse wins
            return True
        if catPos == mousePos:  # Cat wins
            return False
        if turn > 1000:  # Too many turns
            return False
        if (mousePos, catPos, turn % 2) in memo:  # Check memoization
            return memo[(mousePos, catPos, turn % 2)]

        # Determine next moves
        if turn % 2 == 0:  # Mouse's turn
            for jump in range(1, mouseJump + 1):
                for dr in [-1, 0, 1]:
                    for dc in [-1, 0, 1]:
                        if abs(dr) + abs(dc) == 1:  # Move in 4 directions
                            newMousePos = (mousePos[0] + dr * jump, mousePos[1] + dc * jump)
                            if 0 <= newMousePos[0] < rows and 0 <= newMousePos[1] < cols and grid[newMousePos[0]][newMousePos[1]] != '#':
                                if canMouseWin(newMousePos, catPos, turn + 1) == False:
                                    memo[(mousePos, catPos, turn % 2)] = True
                                    return True
            memo[(mousePos, catPos, turn % 2)] = False
            return False
        else:  # Cat's turn
            for jump in range(1, catJump + 1):
                for dr in [-1, 0, 1]:
                    for dc in [-1, 0, 1]:
                        if abs(dr) + abs(dc) == 1:  # Move in 4 directions
                            newCatPos = (catPos[0] + dr * jump, catPos[1] + dc * jump)
                            if 0 <= newCatPos[0] < rows and 0 <= newCatPos[1] < cols and grid[newCatPos[0]][newCatPos[1]] != '#':
                                if newCatPos != mousePos and canMouseWin(mousePos, newCatPos, turn + 1):
                                    memo[(mousePos, catPos, turn % 2)] = False
                                    return False
            memo[(mousePos, catPos, turn % 2)] = True
            return True

    return canMouseWin(mouse, cat, 0)