LeetCode Solutions Blog

Cat and Mouse II

Number: 1727

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Two players – a cat and a mouse – play a game on a grid populated with walls, open spaces, and a single food cell. The grid contains one cat ('C'), one mouse ('M'), and one food ('F'). The mouse moves first, and each player alternates turns. On a turn, a player can choose to remain in place or jump in one of the four cardinal directions (up, down, left, right) by up to a limited number of cells (catJump for the cat and mouseJump for the mouse). Moves cannot pass through walls or leave the grid. The game ends under one of the following conditions:

If the cat moves onto the mouse’s cell, the cat wins.
If the cat reaches the food before the mouse, the cat wins.
If the mouse reaches the food first, the mouse wins.
If the mouse cannot reach the food within 1000 turns, the cat wins. Determining whether the mouse can win (with both players playing optimally) is the goal of this problem.

Key Insights

Represent the state with positions for the mouse and cat along with the current turn.
Use DFS with memoization (or dynamic programming) to explore all game states without re-computation.
Handle each move by simulating all legal jumps (including staying in place).
Incorporate the turn limit (1000 moves) to avoid infinite recursion.
Terminal states are reached when either player reaches the food or the cat catches the mouse.

Space and Time Complexity

Time Complexity: O(rows * cols * rows * cols * 2 * (max(catJump, mouseJump))) – since for each state we might explore several moves. Space Complexity: O(rows * cols * rows * cols * 2) for storing memoized results.

Solution

We solve the problem by modeling it as a game state DFS with memoization. A state is defined by (mouseRow, mouseCol, catRow, catCol, turnCount) with turn alternating between the mouse (even turns) and the cat (odd turns). The DFS function checks:

Terminal conditions (if the mouse or cat has reached the food, or if the cat catches the mouse).
The possibility of exceeding the allowed 1000-turn limit, in which case the cat wins by default.
For the current player's turn, iterate over all possible moves (in each direction, jumping 0 [staying] through jump limit cells, stopping if a wall or boundary is met). If a winning move is found (mouse’s turn leads to a state from which the mouse can force a win, or cat’s turn leads to a state forcing the mouse’s defeat), return the corresponding outcome. The use of recursion with caching of states avoids cycles and redundant computations.

Code Solutions

Below are solutions in various languages.

# Python solution for Cat and Mouse II

class Solution:
    def canMouseWin(self, grid, catJump, mouseJump):
        rows, cols = len(grid), len(grid[0])
        # Find initial positions of mouse, cat and food.
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 'M':
                    mouse_init = (i, j)
                elif grid[i][j] == 'C':
                    cat_init = (i, j)
                elif grid[i][j] == 'F':
                    food = (i, j)
        
        # Memoization: state -> bool . State encodes: (mouse_r, mouse_c, cat_r, cat_c, turn)
        memo = {}
        maxTurns = 1000
        
        # DFS that returns True if Mouse can force a win from state
        def dfs(mouse_r, mouse_c, cat_r, cat_c, turn):
            if turn == maxTurns:
                return False  # mouse loses if game exceeds turn limit
            
            # terminal conditions
            if mouse_r == food[0] and mouse_c == food[1]:
                return True  # mouse wins by reaching food
            if cat_r == food[0] and cat_c == food[1]:
                return False  # cat wins by reaching food first
            if cat_r == mouse_r and cat_c == mouse_c:
                return False  # cat wins by catching mouse
            
            state = (mouse_r, mouse_c, cat_r, cat_c, turn)
            if state in memo:
                return memo[state]
            
            # Determine whose move: even turn -> mouse, odd -> cat.
            if turn % 2 == 0:
                # Mouse's turn: try every possible move, if any results in a win, return True.
                jumpLimit = mouseJump
                cur_r, cur_c = mouse_r, mouse_c
                # Try staying in place
                if dfs(cur_r, cur_c, cat_r, cat_c, turn + 1):
                    memo[state] = True
                    return True
                # Try all 4 directions
                for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
                    for jump in range(1, jumpLimit + 1):
                        new_r = cur_r + dr * jump
                        new_c = cur_c + dc * jump
                        # Check bounds and walls
                        if new_r < 0 or new_r >= rows or new_c < 0 or new_c >= cols or grid[new_r][new_c] == '#':
                            break  # cannot jump further in this direction
                        if dfs(new_r, new_c, cat_r, cat_c, turn + 1):
                            memo[state] = True
                            return True
                memo[state] = False
                return False
            else:
                # Cat's turn: if any move forces mouse to lose, then cat will choose that path.
                jumpLimit = catJump
                cur_r, cur_c = cat_r, cat_c
                # Try staying in place.
                if not dfs(mouse_r, mouse_c, cur_r, cur_c, turn + 1):
                    memo[state] = False
                    return False
                # Try all 4 directions.
                for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
                    for jump in range(1, jumpLimit + 1):
                        new_r = cur_r + dr * jump
                        new_c = cur_c + dc * jump
                        # Check bounds and walls.
                        if new_r < 0 or new_r >= rows or new_c < 0 or new_c >= cols or grid[new_r][new_c] == '#':
                            break
                        if not dfs(mouse_r, mouse_c, new_r, new_c, turn + 1):
                            memo[state] = False
                            return False
                memo[state] = True
                return True
        
        return dfs(mouse_init[0], mouse_init[1], cat_init[0], cat_init[1], 0)
        
# Example usage:
# solution = Solution()
# result = solution.canMouseWin(["####F","#C...","M...."], 1, 2)
# print(result)  # Expected True