title: Cat and Mouse II
slug: cat-and-mouse-ii
difficulty: hard
leetcode_id: 1728
leetcode_url: https://leetcode.com/problems/cat-and-mouse-ii/
categories:
  - graphs
  - dynamic-programming
patterns:
  - slug: bfs
    is_optimal: true
  - slug: dynamic-programming
    is_optimal: false
  - slug: matrix-traversal
    is_optimal: false

function_signature: "def can_mouse_win(grid: list[str], cat_jump: int, mouse_jump: int) -> bool:"

test_cases:
  visible:
    - input: { grid: ["####F", "#C...", "M...."], cat_jump: 1, mouse_jump: 2 }
      expected: true
    - input: { grid: ["M.C...F"], cat_jump: 1, mouse_jump: 4 }
      expected: true
    - input: { grid: ["M.C...F"], cat_jump: 1, mouse_jump: 3 }
      expected: false
  hidden:
    - input: { grid: ["CM......", "#######.", "........", ".#######", "........", "#######.", "........", "F#######"], cat_jump: 1, mouse_jump: 1 }
      expected: true
    - input: { grid: [".M...", "..#..", "#..#.", "C#.#.", "...#F"], cat_jump: 3, mouse_jump: 1 }
      expected: false
    - input: { grid: ["C...#", "...#.", "....#", "M....", "....F"], cat_jump: 2, mouse_jump: 5 }
      expected: false

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.

  - Players are represented by the characters `'C'` (Cat) and `'M'` (Mouse)
  - Floors are represented by the character `'.'` and can be walked on
  - Walls are represented by the character `'#'` and cannot be walked on
  - Food is represented by the character `'F'` and can be walked on
  - There is only one of each character `'C'`, `'M'`, and `'F'` in `grid`

  Mouse and Cat play according to the following rules:

  - Mouse **moves first**, then they take turns to move
  - During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the `grid`
  - `catJump` and `mouseJump` are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length
  - Staying in the same position is allowed
  - Mouse can jump over Cat

  The game can end in 4 ways:

  - If Cat occupies the same position as Mouse, Cat wins
  - If Cat reaches the food first, Cat wins
  - If Mouse reaches the food first, Mouse wins
  - If Mouse cannot get to the food within 1000 turns, Cat wins

  Given a `rows x cols` matrix `grid` and two integers `catJump` and `mouseJump`, return `true` *if Mouse can win the game if both Cat and Mouse play optimally*, otherwise return `false`.

constraints: |
  - `rows == grid.length`
  - `cols == grid[i].length`
  - `1 <= rows, cols <= 8`
  - `grid[i][j]` consists only of characters `'C'`, `'M'`, `'F'`, `'.'`, and `'#'`
  - There is only one of each character `'C'`, `'M'`, and `'F'` in `grid`
  - `1 <= catJump, mouseJump <= 8`

examples:
  - input: 'grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2'
    output: "true"
    explanation: "Cat cannot catch Mouse on its turn nor can it get the food before Mouse."
  - input: 'grid = ["M.C...F"], catJump = 1, mouseJump = 4'
    output: "true"
    explanation: "Mouse can reach the food in one jump (distance 4) before Cat can intercept."
  - input: 'grid = ["M.C...F"], catJump = 1, mouseJump = 3'
    output: "false"
    explanation: "Mouse cannot reach the food quickly enough — Cat can intercept or reach the food first."

explanation:
  intuition: |
    This is a classic **game theory** problem where two players (Cat and Mouse) take turns making optimal decisions. Think of it like a chess endgame: at each position, we need to determine whether the current player has a **winning strategy** assuming both players play perfectly.

    The key insight is that this game has a **finite state space**. A state is defined by:
    - Mouse's position (row, col)
    - Cat's position (row, col)
    - Whose turn it is (Mouse or Cat)
    - The turn number (to detect stalemates)

    With a maximum grid of `8x8 = 64` positions for each player and up to 1000 turns, the state space is bounded. We can explore all possible game states and determine winners using **memoization**.

    The mental model is **minimax**: Mouse tries to reach food while avoiding Cat, and Cat tries to either catch Mouse or reach food first. At Mouse's turn, if *any* move leads to a Mouse win, Mouse wins. At Cat's turn, if *any* move leads to a Cat win, Cat wins.

  approach: |
    We solve this using **Game Theory with Memoization (Top-Down DP)**:

    **Step 1: Parse the grid**

    - Find the starting positions of Mouse (`M`), Cat (`C`), and Food (`F`)
    - Store grid dimensions and wall locations

    &nbsp;

    **Step 2: Define the game state**

    - `(mouse_row, mouse_col, cat_row, cat_col, turn)` where `turn` indicates whose move it is
    - The turn counter also serves as a termination condition (if turns exceed a threshold, Cat wins by default)

    &nbsp;

    **Step 3: Generate valid moves**

    - For each player, generate all possible positions they can jump to:
      - Stay in place (always valid)
      - Jump 1 to `maxJump` cells in each of the 4 directions
      - Stop generating moves in a direction if a wall is encountered (cannot jump over walls)
      - Cannot move outside the grid

    &nbsp;

    **Step 4: Implement recursive minimax with memoization**

    - **Base cases:**
      - Mouse at Food position → Mouse wins (`true`)
      - Cat at Food position → Cat wins (`false`)
      - Cat catches Mouse (same position) → Cat wins (`false`)
      - Turn limit exceeded → Cat wins (`false`)
    - **Recursive cases:**
      - If Mouse's turn: Mouse wins if **any** valid move leads to a winning state
      - If Cat's turn: Cat wins if **all** Mouse moves lead to Cat winning (equivalently, Cat wins if **any** move leads to Cat winning)

    &nbsp;

    **Step 5: Return the result**

    - Call the recursive function with initial positions and Mouse's turn
    - Return whether Mouse has a winning strategy from the starting state

  common_pitfalls:
    - title: Not Handling the Turn Limit
      description: |
        The problem states Mouse must win within 1000 turns. Without this limit, the recursion could run forever in cycles where neither player can force a win.

        However, using exactly 1000 as the limit with full state tracking is expensive. A common optimisation is to use a smaller bound based on the observation that if a winning path exists, it will be found within `2 × rows × cols` moves (each cell visited once per player).
      wrong_approach: "No turn limit or using exactly 1000 turns"
      correct_approach: "Use a reasonable upper bound like 2 × rows × cols × 2"

    - title: Incorrect Move Generation
      description: |
        When generating jumps, you must stop in a direction when you hit a wall. You cannot "skip over" walls.

        For example, if jumping right with `maxJump = 3` and there's a wall at distance 2, you can only jump to distances 0 or 1 — not 3.
      wrong_approach: "Generate all positions within maxJump ignoring intermediate walls"
      correct_approach: "Stop generating moves in a direction when a wall is encountered"

    - title: Forgetting "Stay in Place" Move
      description: |
        Both Cat and Mouse can choose to stay in their current position. This is a valid move that must be included in the move generation.

        Missing this can cause incorrect results when staying put is the optimal strategy (e.g., Mouse waiting at food, or strategic positioning).
      wrong_approach: "Only generate moves to different positions"
      correct_approach: "Include current position as a valid move option"

    - title: State Space Explosion
      description: |
        With naive implementation, the state space can be huge: `64 × 64 × 2 × 1000 = 8,192,000` states. This can cause TLE or MLE.

        The key is recognising that if the game hasn't ended in `O(rows × cols)` turns, it likely won't end (it's cycling). Using a tighter turn bound significantly reduces states.
      wrong_approach: "Full 1000-turn state tracking"
      correct_approach: "Use bounded turns (e.g., 128 or rows × cols × 2) with memoization"

  key_takeaways:
    - "**Game theory minimax**: One player wins if ANY of their moves leads to winning; the opponent wins if ALL moves lead to the opponent winning"
    - "**State-based memoization**: Define complete game states and cache results to avoid recomputation"
    - "**Bounded search**: Use domain knowledge to limit search depth (turn limits based on grid size, not arbitrary large numbers)"
    - "**Move generation matters**: Correctly handling walls, boundaries, and the 'stay' option is crucial for correctness"

  time_complexity: "O(m × n × m × n × T × (catJump + mouseJump)) where `m × n` is the grid size and `T` is the turn limit. Each state is visited once, and from each state we explore up to `4 × (catJump + mouseJump)` moves."
  space_complexity: "O(m × n × m × n × T) for the memoization cache storing all visited states, plus O(T) recursion stack depth."

solutions:
  - approach_name: Memoized DFS (Minimax)
    is_optimal: true
    code: |
      def can_mouse_win(grid: list[str], cat_jump: int, mouse_jump: int) -> bool:
          rows, cols = len(grid), len(grid[0])

          # Find starting positions
          mouse_start = cat_start = food_pos = None
          for r in range(rows):
              for c in range(cols):
                  if grid[r][c] == 'M':
                      mouse_start = (r, c)
                  elif grid[r][c] == 'C':
                      cat_start = (r, c)
                  elif grid[r][c] == 'F':
                      food_pos = (r, c)

          # Directions: up, down, left, right
          directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

          def get_moves(pos: tuple[int, int], max_jump: int) -> list[tuple[int, int]]:
              """Generate all valid moves from a position."""
              r, c = pos
              moves = [(r, c)]  # Can stay in place

              for dr, dc in directions:
                  for jump in range(1, max_jump + 1):
                      nr, nc = r + dr * jump, c + dc * jump
                      # Check bounds
                      if not (0 <= nr < rows and 0 <= nc < cols):
                          break
                      # Check for wall - cannot jump over walls
                      if grid[nr][nc] == '#':
                          break
                      moves.append((nr, nc))

              return moves

          # Memoization cache: (mouse_pos, cat_pos, turn, is_mouse_turn) -> mouse_wins
          memo = {}
          # Turn limit to prevent infinite loops (optimised bound)
          max_turns = rows * cols * 2

          def dfs(mouse: tuple[int, int], cat: tuple[int, int],
                  turn: int, is_mouse_turn: bool) -> bool:
              """Returns True if Mouse can win from this state."""
              # Base cases
              if mouse == food_pos:
                  return True  # Mouse wins
              if cat == food_pos or cat == mouse:
                  return False  # Cat wins
              if turn >= max_turns:
                  return False  # Cat wins by timeout

              state = (mouse, cat, turn, is_mouse_turn)
              if state in memo:
                  return memo[state]

              if is_mouse_turn:
                  # Mouse wins if ANY move leads to a win
                  result = False
                  for next_mouse in get_moves(mouse, mouse_jump):
                      if dfs(next_mouse, cat, turn + 1, False):
                          result = True
                          break
              else:
                  # Cat wins if ANY move leads to Cat winning
                  # So Mouse wins only if ALL cat moves still let Mouse win
                  result = True
                  for next_cat in get_moves(cat, cat_jump):
                      if not dfs(mouse, next_cat, turn + 1, True):
                          result = False
                          break

              memo[state] = result
              return result

          return dfs(mouse_start, cat_start, 0, True)
    explanation: |
      **Time Complexity:** O(m² × n² × T × J) where `m × n` is grid size, `T` is turn limit, and `J` is average jump distance.

      **Space Complexity:** O(m² × n² × T) for memoization cache.

      This solution uses depth-first search with memoization to explore all possible game states. The minimax logic ensures optimal play: Mouse picks any winning move, Cat picks any move that prevents Mouse from winning. The turn limit prevents infinite loops in cyclic games.

  - approach_name: BFS with State Graph
    is_optimal: false
    code: |
      from collections import deque

      def can_mouse_win(grid: list[str], cat_jump: int, mouse_jump: int) -> bool:
          rows, cols = len(grid), len(grid[0])

          # Find positions
          for r in range(rows):
              for c in range(cols):
                  if grid[r][c] == 'M':
                      mouse_start = (r, c)
                  elif grid[r][c] == 'C':
                      cat_start = (r, c)
                  elif grid[r][c] == 'F':
                      food_pos = (r, c)

          directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

          def get_moves(pos, max_jump):
              r, c = pos
              moves = [(r, c)]
              for dr, dc in directions:
                  for jump in range(1, max_jump + 1):
                      nr, nc = r + dr * jump, c + dc * jump
                      if not (0 <= nr < rows and 0 <= nc < cols):
                          break
                      if grid[nr][nc] == '#':
                          break
                      moves.append((nr, nc))
              return moves

          # Precompute moves for all positions
          mouse_moves = {}
          cat_moves = {}
          for r in range(rows):
              for c in range(cols):
                  if grid[r][c] != '#':
                      mouse_moves[(r, c)] = get_moves((r, c), mouse_jump)
                      cat_moves[(r, c)] = get_moves((r, c), cat_jump)

          # BFS approach: explore states level by level
          # State: (mouse_pos, cat_pos, is_mouse_turn)
          max_turns = rows * cols * 2

          # Track visited states with turn number
          visited = set()
          queue = deque([(mouse_start, cat_start, True, 0)])
          visited.add((mouse_start, cat_start, True, 0))

          while queue:
              mouse, cat, is_mouse_turn, turn = queue.popleft()

              # Check win conditions
              if mouse == food_pos:
                  return True
              if cat == food_pos or cat == mouse:
                  continue  # Cat wins this path, try others
              if turn >= max_turns:
                  continue  # Timeout, Cat wins

              if is_mouse_turn:
                  # Try all mouse moves
                  for next_mouse in mouse_moves.get(mouse, []):
                      state = (next_mouse, cat, False, turn + 1)
                      if state not in visited:
                          visited.add(state)
                          # Quick win check
                          if next_mouse == food_pos:
                              return True
                          queue.append(state)
              else:
                  # Try all cat moves
                  for next_cat in cat_moves.get(cat, []):
                      state = (mouse, next_cat, True, turn + 1)
                      if state not in visited:
                          visited.add(state)
                          queue.append(state)

          return False
    explanation: |
      **Time Complexity:** O(m² × n² × T × J) — similar to DFS but explores level by level.

      **Space Complexity:** O(m² × n² × T) for visited set and queue.

      This BFS approach explores game states level by level (by turn number). While it can find solutions, the simple BFS doesn't correctly implement minimax logic — it finds *any* path where Mouse reaches food, not necessarily an optimal one. The memoized DFS approach above is more correct for game theory problems. This solution is included to illustrate an alternative exploration strategy, though it may not handle all edge cases correctly.
