Facebook Pixel

1728. Cat and Mouse II

HardGraphTopological SortMemoizationArrayMathDynamic ProgrammingGame TheoryMatrix
Leetcode Link

Problem Description

This is a strategic game between a cat and a mouse on a grid. The grid contains:

  • 'C' - Cat's starting position
  • 'M' - Mouse's starting position
  • 'F' - Food location
  • '.' - Floor (walkable)
  • '#' - Wall (not walkable)

Game Rules:

  1. Mouse moves first, then they alternate turns
  2. Each player can jump up to their maximum jump distance (mouseJump or catJump) in one of four directions (up, down, left, right)
  3. Players can choose to jump any distance from 0 (stay in place) to their maximum
  4. Players cannot jump through walls or outside the grid
  5. Mouse can jump over Cat (but not vice versa)

Winning Conditions:

  • Cat wins if:
    • Cat catches Mouse (occupies same position)
    • Cat reaches the food first
    • Mouse doesn't reach food within 1000 turns
  • Mouse wins if:
    • Mouse reaches the food first

The problem asks: Given the grid and jump distances, determine if Mouse can win when both players play optimally. Return true if Mouse can win, false otherwise.

The solution uses game theory and dynamic programming to model all possible game states as (mouse_position, cat_position, whose_turn). It works backwards from terminal states (where the winner is known) to determine the outcome of the initial state. The algorithm uses BFS and degree counting to propagate winning/losing states through the game tree, considering that:

  • A player wins if they can move to any winning state
  • A player loses if all possible moves lead to losing states

The final answer is determined by checking the outcome of the initial state (mouse_start, cat_start, mouse_turn).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To solve this game problem, we need to think about it from a game theory perspective. Since both players play optimally, we need to determine who has a winning strategy from any given position.

The key insight is that this is a finite, deterministic game - there are a limited number of possible game states, and from each state, the outcome is predetermined if both players play perfectly. Each game state can be represented as a tuple: (mouse_position, cat_position, whose_turn).

We can work backwards from the end states where we know the winner for certain:

  • If mouse reaches food → mouse wins
  • If cat reaches food → cat wins
  • If cat catches mouse → cat wins

From these terminal states, we can propagate the winning/losing information backwards. The reasoning is:

  • If it's your turn and you can move to a state where you win, then the current state is a winning state for you
  • If it's your turn and all your possible moves lead to states where you lose, then the current state is a losing state for you

This naturally leads to a BFS approach starting from terminal states. However, there's a subtlety: when determining if a state is losing, we need to ensure we've checked ALL possible moves. This is where the degree counting technique comes in:

  • We track how many possible moves each player has from each state
  • A state becomes a losing state only when its degree (count of unchecked moves) reaches 0, meaning all moves have been confirmed as losing

The algorithm assigns values to states:

  • 0 = unknown
  • 1 = mouse wins
  • 2 = cat wins

By processing states level by level through BFS and carefully tracking degrees, we can determine the outcome of the initial state (mouse_start, cat_start, mouse_turn=0). If this evaluates to 1, mouse can win with optimal play.

Learn more about Graph, Topological Sort, Memoization, Math and Dynamic Programming patterns.

Solution Approach

The implementation consists of two main parts: preprocessing the graph and calculating the game outcome using BFS with degree counting.

1. Graph Construction:

First, we build adjacency lists for both mouse and cat movements from each position:

g_mouse = [[] for _ in range(m * n)]  # Mouse's possible moves from each position
g_cat = [[] for _ in range(m * n)]    # Cat's possible moves from each position

Each grid position (i, j) is mapped to a single integer i * n + j for easier state representation. For each valid position, we compute all reachable positions within the jump limit:

  • Iterate through four directions using dirs = (-1, 0, 1, 0, -1) with pairwise
  • For each direction, try jumping distances from 0 to mouseJump/catJump
  • Stop if we hit a wall or grid boundary
  • Add all valid positions to the respective adjacency list

2. Game State Calculation:

The calc function implements the backward induction algorithm:

Initialize degree matrix:

degree[i][j][0] = len(g_mouse[i])  # Mouse's turn, count of mouse's moves
degree[i][j][1] = len(g_cat[j])     # Cat's turn, count of cat's moves

Set terminal states:

ans[hole][i][1] = 1  # Mouse at food, any cat position, cat's turn → mouse wins
ans[i][hole][0] = 2  # Cat at food, any mouse position, mouse's turn → cat wins
ans[i][i][0] = ans[i][i][1] = 2  # Same position → cat wins (caught mouse)

BFS propagation: Starting from terminal states in the queue, for each state we:

  1. Find all previous states that could lead to the current state using get_prev_states:

    • If current turn is cat's (t=1), previous states are all positions cat could have come from
    • If current turn is mouse's (t=0), previous states are all positions mouse could have come from

  2. For each previous state:

    • If the previous player can move to a winning state (pt == t - 1), mark it as winning immediately
    • Otherwise, decrement the degree counter
    • If degree reaches 0 (all moves explored and all are losing), mark the state as losing

3. Result:

The final answer is obtained by checking ans[mouse_start][cat_start][0]:

  • Returns 1 if mouse wins from the initial position
  • Returns 2 if cat wins from the initial position

The algorithm guarantees correctness because:

  • It explores all reachable states from terminal positions
  • It correctly identifies winning states (any winning move available)
  • It correctly identifies losing states (all moves lead to opponent winning)
  • The degree counting ensures we don't prematurely mark a state as losing

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let me walk through a small example to illustrate the solution approach.

Consider this simple 2x3 grid:

C . F
# . M

With mouseJump = 1 and catJump = 1.

Step 1: Convert grid positions to indices

  • Cat starts at (0,0) → index 0
  • Mouse starts at (1,2) → index 5
  • Food is at (0,2) → index 2
  • Wall at (1,0) → index 3

Step 2: Build adjacency lists

For Mouse from position 5 (1,2):

  • Can jump to: 5 (stay), 4 (left one), 2 (up one)
  • g_mouse[5] = [5, 4, 2]

For Cat from position 0 (0,0):

  • Can jump to: 0 (stay), 1 (right one)
  • Cannot jump down (wall blocks)
  • g_cat[0] = [0, 1]

Step 3: Initialize degrees

  • degree[5][0][0] = 3 (mouse at 5, has 3 moves)
  • degree[5][0][1] = 2 (cat at 0, has 2 moves)

Step 4: Set terminal states and process BFS

Terminal states added to queue:

  • ans[2][0][1] = 1 (mouse at food, cat at 0, cat's turn → mouse wins)
  • ans[5][2][0] = 2 (cat at food, mouse at 5, mouse's turn → cat wins)

Processing from queue:

From state (2,0,1) where mouse wins:

  • Previous states: positions mouse could have come from to reach food
  • State (5,0,0): mouse's turn, can move to winning state (2,0,1)
  • Mark ans[5][0][0] = 1 (mouse wins!)

From state (5,2,0) where cat wins:

  • Previous states: positions cat could have come from to reach food
  • State (5,1,1): cat at 1, can move to 2 (food) → cat wins
  • Mark ans[5][1][1] = 2

Continue processing until queue is empty.

Step 5: Check initial state

  • Initial state is (5,0,0) - mouse at 5, cat at 0, mouse's turn
  • We found ans[5][0][0] = 1
  • Therefore, mouse can win with optimal play!

The key insight: Mouse can reach the food in one jump from position 5 to position 2, while cat needs at least 2 moves from position 0. Since mouse moves first and plays optimally, mouse wins.

Template Solution

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        # Step 1: Parse grid and find initial positions
        m, n = len(grid), len(grid[0])
        mouse_start = cat_start = food = 0
      
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'M':
                    mouse_start = i * n + j
                elif grid[i][j] == 'C':
                    cat_start = i * n + j
                elif grid[i][j] == 'F':
                    food = i * n + j
      
        # Step 2: Build adjacency lists for valid moves
        def build_graph(max_jump):
            graph = [[] for _ in range(m * n)]
            dirs = (-1, 0, 1, 0, -1)
          
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == '#':
                        continue
                    pos = i * n + j
                    graph[pos].append(pos)  # Can stay in place
                  
                    for dx, dy in zip(dirs, dirs[1:]):
                        for jump in range(1, max_jump + 1):
                            ni, nj = i + dx * jump, j + dy * jump
                            if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != '#':
                                graph[pos].append(ni * n + nj)
                            else:
                                break  # Can't jump through walls
            return graph
      
        g_mouse = build_graph(mouseJump)
        g_cat = build_graph(catJump)
      
        # Step 3: Game state calculation with BFS
        # ans[i][j][k]: outcome when mouse at i, cat at j, turn k (0=mouse, 1=cat)
        # 0=unknown, 1=mouse wins, 2=cat wins
        ans = [[[0] * 2 for _ in range(m * n)] for _ in range(m * n)]
        degree = [[[0] * 2 for _ in range(m * n)] for _ in range(m * n)]
      
        # Initialize degrees
        for i in range(m * n):
            for j in range(m * n):
                degree[i][j][0] = len(g_mouse[i])
                degree[i][j][1] = len(g_cat[j])
      
        # Set terminal states
        queue = deque()
        for i in range(m * n):
            for t in range(2):
                # Mouse reaches food
                ans[food][i][t] = 1
                queue.append((food, i, t))
                # Cat reaches food
                if i != food:
                    ans[i][food][t] = 2
                    queue.append((i, food, t))
                # Cat catches mouse
                if i > 0:
                    ans[i][i][t] = 2
                    queue.append((i, i, t))
      
        # BFS to propagate outcomes
        while queue:
            mouse, cat, turn = queue.popleft()
            current_result = ans[mouse][cat][turn]
          
            # Get previous states
            if turn == 1:  # Was cat's turn, so previous was mouse's turn
                for prev_mouse in g_mouse[mouse]:
                    if ans[prev_mouse][cat][0]:
                        continue
                    if current_result == 1:  # Mouse wins
                        ans[prev_mouse][cat][0] = 1
                        queue.append((prev_mouse, cat, 0))
                    else:
                        degree[prev_mouse][cat][0] -= 1
                        if degree[prev_mouse][cat][0] == 0:
                            ans[prev_mouse][cat][0] = 2
                            queue.append((prev_mouse, cat, 0))
            else:  # Was mouse's turn, so previous was cat's turn
                for prev_cat in g_cat[cat]:
                    if ans[mouse][prev_cat][1]:
                        continue
                    if current_result == 2:  # Cat wins
                        ans[mouse][prev_cat][1] = 2
                        queue.append((mouse, prev_cat, 1))
                    else:
                        degree[mouse][prev_cat][1] -= 1
                        if degree[mouse][prev_cat][1] == 0:
                            ans[mouse][prev_cat][1] = 1
                            queue.append((mouse, prev_cat, 1))
      
        # Check if mouse wins from initial state
        return ans[mouse_start][cat_start][0] == 1

Solution Implementation

1class Solution:
2    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
3        """
4        Determine if the mouse can win the game.
5      
6        Args:
7            grid: 2D grid where 'M' is mouse, 'C' is cat, 'F' is food, '#' is wall
8            catJump: Maximum jump distance for cat
9            mouseJump: Maximum jump distance for mouse
10          
11        Returns:
12            True if mouse can win, False otherwise
13        """
14        rows, cols = len(grid), len(grid[0])
15        cat_position = mouse_position = food_position = 0
16      
17        # Direction vectors for 4 directions (up, right, down, left)
18        directions = (-1, 0, 1, 0, -1)
19      
20        # Build adjacency lists for mouse and cat movements
21        mouse_graph = [[] for _ in range(rows * cols)]
22        cat_graph = [[] for _ in range(rows * cols)]
23      
24        # Parse grid and build movement graphs
25        for row_idx, row in enumerate(grid):
26            for col_idx, cell in enumerate(row):
27                if cell == "#":  # Skip walls
28                    continue
29                  
30                # Convert 2D position to 1D index
31                current_pos = row_idx * cols + col_idx
32              
33                # Record special positions
34                if cell == "C":
35                    cat_position = current_pos
36                elif cell == "M":
37                    mouse_position = current_pos
38                elif cell == "F":
39                    food_position = current_pos
40              
41                # Build possible moves for both mouse and cat
42                for dx, dy in pairwise(directions):
43                    # Add mouse's possible moves (including stay at same position)
44                    for jump_dist in range(mouseJump + 1):
45                        new_row, new_col = row_idx + jump_dist * dx, col_idx + jump_dist * dy
46                      
47                        # Check boundaries and walls
48                        if not (0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != "#"):
49                            break
50                        mouse_graph[current_pos].append(new_row * cols + new_col)
51                  
52                    # Add cat's possible moves (including stay at same position)
53                    for jump_dist in range(catJump + 1):
54                        new_row, new_col = row_idx + jump_dist * dx, col_idx + jump_dist * dy
55                      
56                        # Check boundaries and walls
57                        if not (0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != "#"):
58                            break
59                        cat_graph[current_pos].append(new_row * cols + new_col)
60      
61        # Calculate game outcome using minimax algorithm
62        result = self.calc(mouse_graph, cat_graph, mouse_position, cat_position, food_position)
63        return result == 1  # Return True if mouse wins (result == 1)
64  
65    def calc(
66        self,
67        mouse_graph: List[List[int]],
68        cat_graph: List[List[int]],
69        mouse_start: int,
70        cat_start: int,
71        food_pos: int,
72    ) -> int:
73        """
74        Calculate game outcome using retrograde analysis.
75      
76        Args:
77            mouse_graph: Adjacency list for mouse movements
78            cat_graph: Adjacency list for cat movements
79            mouse_start: Mouse starting position
80            cat_start: Cat starting position
81            food_pos: Food position
82          
83        Returns:
84            1 if mouse wins, 2 if cat wins, 0 if draw
85        """
86      
87        def get_previous_states(state):
88            """
89            Get all possible previous states that could lead to current state.
90          
91            Args:
92                state: Tuple of (mouse_pos, cat_pos, turn)
93              
94            Returns:
95                List of previous states
96            """
97            mouse_pos, cat_pos, turn = state
98            previous_turn = turn ^ 1  # Toggle turn (0->1 or 1->0)
99            previous_states = []
100          
101            if previous_turn == 1:  # Previous turn was cat's
102                # Find all positions cat could have been at
103                for prev_cat_pos in cat_graph[cat_pos]:
104                    if game_results[mouse_pos][prev_cat_pos][1] == 0:
105                        previous_states.append((mouse_pos, prev_cat_pos, previous_turn))
106            else:  # Previous turn was mouse's
107                # Find all positions mouse could have been at
108                for prev_mouse_pos in mouse_graph[mouse_pos]:
109                    if game_results[prev_mouse_pos][cat_pos][0] == 0:
110                        previous_states.append((prev_mouse_pos, cat_pos, 0))
111          
112            return previous_states
113      
114        num_positions = len(mouse_graph)
115      
116        # Initialize degree array (number of possible moves from each state)
117        # degree[mouse_pos][cat_pos][turn] = number of moves
118        degree = [[[0, 0] for _ in range(num_positions)] for _ in range(num_positions)]
119        for mouse_pos in range(num_positions):
120            for cat_pos in range(num_positions):
121                degree[mouse_pos][cat_pos][0] = len(mouse_graph[mouse_pos])  # Mouse's turn
122                degree[mouse_pos][cat_pos][1] = len(cat_graph[cat_pos])      # Cat's turn
123      
124        # Initialize game results array
125        # game_results[mouse_pos][cat_pos][turn] = outcome (0: unknown, 1: mouse wins, 2: cat wins)
126        game_results = [[[0, 0] for _ in range(num_positions)] for _ in range(num_positions)]
127      
128        # Queue for BFS
129        queue = deque()
130      
131        # Initialize terminal states
132        for pos in range(num_positions):
133            # Mouse reaches food (mouse wins regardless of cat position)
134            game_results[food_pos][pos][1] = 1
135            queue.append((food_pos, pos, 1))
136          
137            # Cat reaches food (cat wins)
138            game_results[pos][food_pos][0] = 2
139            queue.append((pos, food_pos, 0))
140          
141            # Mouse and cat at same position (cat wins)
142            game_results[pos][pos][0] = game_results[pos][pos][1] = 2
143            queue.append((pos, pos, 0))
144            queue.append((pos, pos, 1))
145      
146        # Perform retrograde analysis using BFS
147        while queue:
148            current_state = queue.popleft()
149            current_result = game_results[current_state[0]][current_state[1]][current_state[2]]
150          
151            # Process all states that could lead to current state
152            for prev_state in get_previous_states(current_state):
153                prev_mouse_pos, prev_cat_pos, prev_turn = prev_state
154              
155                # If previous player can force the same outcome
156                if prev_turn == current_result - 1:
157                    game_results[prev_mouse_pos][prev_cat_pos][prev_turn] = current_result
158                    queue.append(prev_state)
159                else:
160                    # Decrease degree (one less option leads to unfavorable outcome)
161                    degree[prev_mouse_pos][prev_cat_pos][prev_turn] -= 1
162                  
163                    # If all moves lead to unfavorable outcome
164                    if degree[prev_mouse_pos][prev_cat_pos][prev_turn] == 0:
165                        game_results[prev_mouse_pos][prev_cat_pos][prev_turn] = current_result
166                        queue.append(prev_state)
167      
168        # Return result for initial state (mouse's turn)
169        return game_results[mouse_start][cat_start][0]
170
1class Solution {
2    // Direction vectors for moving up, right, down, left
3    private final int[] directions = {-1, 0, 1, 0, -1};
4
5    /**
6     * Determines if the mouse can win the game given the grid and jump constraints
7     * @param grid The game board with 'M' for mouse, 'C' for cat, 'F' for food, '#' for wall
8     * @param catJump Maximum distance the cat can jump in one move
9     * @param mouseJump Maximum distance the mouse can jump in one move
10     * @return true if mouse can win, false otherwise
11     */
12    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
13        int rows = grid.length;
14        int cols = grid[0].length();
15        int catStartPosition = 0, mouseStartPosition = 0, foodPosition = 0;
16      
17        // Create adjacency lists for possible moves for mouse and cat
18        List<Integer>[] mouseGraph = new List[rows * cols];
19        List<Integer>[] catGraph = new List[rows * cols];
20        Arrays.setAll(mouseGraph, i -> new ArrayList<>());
21        Arrays.setAll(catGraph, i -> new ArrayList<>());
22
23        // Build the graph and find initial positions
24        for (int row = 0; row < rows; row++) {
25            for (int col = 0; col < cols; col++) {
26                char cell = grid[row].charAt(col);
27                if (cell == '#') {
28                    continue; // Skip walls
29                }
30              
31                // Convert 2D position to 1D
32                int currentPosition = row * cols + col;
33              
34                // Mark special positions
35                if (cell == 'C') {
36                    catStartPosition = currentPosition;
37                } else if (cell == 'M') {
38                    mouseStartPosition = currentPosition;
39                } else if (cell == 'F') {
40                    foodPosition = currentPosition;
41                }
42
43                // Build possible moves in all four directions
44                for (int direction = 0; direction < 4; direction++) {
45                    // Add all possible mouse moves from current position
46                    for (int jumpDistance = 0; jumpDistance <= mouseJump; jumpDistance++) {
47                        int newRow = row + jumpDistance * directions[direction];
48                        int newCol = col + jumpDistance * directions[direction + 1];
49                      
50                        // Check boundaries and walls
51                        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || 
52                            grid[newRow].charAt(newCol) == '#') {
53                            break;
54                        }
55                        mouseGraph[currentPosition].add(newRow * cols + newCol);
56                    }
57                  
58                    // Add all possible cat moves from current position
59                    for (int jumpDistance = 0; jumpDistance <= catJump; jumpDistance++) {
60                        int newRow = row + jumpDistance * directions[direction];
61                        int newCol = col + jumpDistance * directions[direction + 1];
62                      
63                        // Check boundaries and walls
64                        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || 
65                            grid[newRow].charAt(newCol) == '#') {
66                            break;
67                        }
68                        catGraph[currentPosition].add(newRow * cols + newCol);
69                    }
70                }
71            }
72        }
73
74        // Calculate the game outcome using minimax algorithm
75        return calc(mouseGraph, catGraph, mouseStartPosition, catStartPosition, foodPosition) == 1;
76    }
77
78    /**
79     * Calculates the game outcome using backward induction (minimax with topological sort)
80     * @param mouseGraph Adjacency list for mouse moves
81     * @param catGraph Adjacency list for cat moves
82     * @param mouseStart Starting position of mouse
83     * @param catStart Starting position of cat
84     * @param foodPos Position of food
85     * @return 1 if mouse wins, 2 if cat wins, 0 if draw
86     */
87    private int calc(List<Integer>[] mouseGraph, List<Integer>[] catGraph, 
88                     int mouseStart, int catStart, int foodPos) {
89        int totalPositions = mouseGraph.length;
90      
91        // degree[mousePos][catPos][turn] = number of outgoing edges
92        // turn: 0 = mouse's turn, 1 = cat's turn
93        int[][][] outDegree = new int[totalPositions][totalPositions][2];
94      
95        // result[mousePos][catPos][turn] = game outcome (0=unknown, 1=mouse wins, 2=cat wins)
96        int[][][] result = new int[totalPositions][totalPositions][2];
97      
98        // Queue for BFS traversal
99        Deque<int[]> queue = new ArrayDeque<>();
100
101        // Initialize out-degrees for each state
102        for (int mousePos = 0; mousePos < totalPositions; mousePos++) {
103            for (int catPos = 0; catPos < totalPositions; catPos++) {
104                outDegree[mousePos][catPos][0] = mouseGraph[mousePos].size();
105                outDegree[mousePos][catPos][1] = catGraph[catPos].size();
106            }
107        }
108
109        // Initialize terminal states and add them to queue
110        for (int pos = 0; pos < totalPositions; pos++) {
111            // Mouse reaches food (mouse wins regardless of whose turn)
112            result[foodPos][pos][1] = 1;
113            queue.offer(new int[] {foodPos, pos, 1});
114          
115            // Cat reaches food (cat wins on mouse's turn)
116            result[pos][foodPos][0] = 2;
117            queue.offer(new int[] {pos, foodPos, 0});
118          
119            // Mouse and cat at same position (cat wins)
120            result[pos][pos][0] = 2;
121            result[pos][pos][1] = 2;
122            queue.offer(new int[] {pos, pos, 0});
123            queue.offer(new int[] {pos, pos, 1});
124        }
125
126        // Process states using backward induction
127        while (!queue.isEmpty()) {
128            int[] currentState = queue.poll();
129            int mousePos = currentState[0];
130            int catPos = currentState[1];
131            int turn = currentState[2];
132            int currentResult = result[mousePos][catPos][turn];
133          
134            // Process all states that can lead to current state
135            for (int[] previousState : getPrevStates(mouseGraph, catGraph, currentState, result)) {
136                int prevMousePos = previousState[0];
137                int prevCatPos = previousState[1];
138                int prevTurn = previousState[2];
139              
140                // If previous player can achieve their winning result
141                if (prevTurn == currentResult - 1) {
142                    result[prevMousePos][prevCatPos][prevTurn] = currentResult;
143                    queue.offer(previousState);
144                } else {
145                    // Decrease the out-degree
146                    outDegree[prevMousePos][prevCatPos][prevTurn]--;
147                  
148                    // If all moves lead to opponent's win
149                    if (outDegree[prevMousePos][prevCatPos][prevTurn] == 0) {
150                        result[prevMousePos][prevCatPos][prevTurn] = currentResult;
151                        queue.offer(previousState);
152                    }
153                }
154            }
155        }
156
157        return result[mouseStart][catStart][0];
158    }
159
160    /**
161     * Gets all possible previous states that can lead to the current state
162     * @param mouseGraph Adjacency list for mouse moves
163     * @param catGraph Adjacency list for cat moves
164     * @param state Current state [mousePos, catPos, turn]
165     * @param result Current game results
166     * @return List of previous states
167     */
168    private List<int[]> getPrevStates(List<Integer>[] mouseGraph, List<Integer>[] catGraph, 
169                                      int[] state, int[][][] result) {
170        int mousePos = state[0];
171        int catPos = state[1];
172        int turn = state[2];
173        int previousTurn = turn ^ 1; // Toggle turn (0->1, 1->0)
174      
175        List<int[]> previousStates = new ArrayList<>();
176      
177        if (previousTurn == 1) {
178            // If previous turn was cat's turn, cat moved to current catPos
179            for (int prevCatPos : catGraph[catPos]) {
180                if (result[mousePos][prevCatPos][1] == 0) {
181                    previousStates.add(new int[] {mousePos, prevCatPos, previousTurn});
182                }
183            }
184        } else {
185            // If previous turn was mouse's turn, mouse moved to current mousePos
186            for (int prevMousePos : mouseGraph[mousePos]) {
187                if (result[prevMousePos][catPos][0] == 0) {
188                    previousStates.add(new int[] {prevMousePos, catPos, 0});
189                }
190            }
191        }
192      
193        return previousStates;
194    }
195}
196
1class Solution {
2private:
3    // Direction vectors for moving up, right, down, left
4    const int directions[5] = {-1, 0, 1, 0, -1};
5
6    /**
7     * Calculate the game outcome using backward induction (minimax with DP)
8     * Returns: 1 if mouse wins, 2 if cat wins, 0 if draw
9     */
10    int calculateGameOutcome(vector<vector<int>>& mouseGraph, vector<vector<int>>& catGraph, 
11                            int mouseStart, int catStart, int foodPos) {
12        int totalNodes = mouseGraph.size();
13      
14        // degree[mouse][cat][turn]: number of next states from current state
15        // turn: 0 = mouse's turn, 1 = cat's turn
16        vector<vector<vector<int>>> degree(totalNodes, vector<vector<int>>(totalNodes, vector<int>(2)));
17      
18        // result[mouse][cat][turn]: game outcome from this state
19        // 0 = unknown, 1 = mouse wins, 2 = cat wins
20        vector<vector<vector<int>>> result(totalNodes, vector<vector<int>>(totalNodes, vector<int>(2)));
21      
22        // Queue for BFS traversal of game states
23        queue<tuple<int, int, int>> stateQueue;
24
25        // Initialize degree counts for each state
26        for (int mousePos = 0; mousePos < totalNodes; mousePos++) {
27            for (int catPos = 0; catPos < totalNodes; catPos++) {
28                degree[mousePos][catPos][0] = mouseGraph[mousePos].size();  // Mouse's turn
29                degree[mousePos][catPos][1] = catGraph[catPos].size();      // Cat's turn
30            }
31        }
32
33        // Initialize terminal states and add them to queue
34        for (int pos = 0; pos < totalNodes; pos++) {
35            // Mouse reaches food (mouse wins) - cat's turn doesn't matter
36            result[foodPos][pos][1] = 1;
37            stateQueue.push(make_tuple(foodPos, pos, 1));
38          
39            // Cat reaches food (cat wins) - mouse's turn
40            result[pos][foodPos][0] = 2;
41            stateQueue.push(make_tuple(pos, foodPos, 0));
42          
43            // Cat catches mouse (cat wins) - both turns
44            result[pos][pos][0] = 2;
45            result[pos][pos][1] = 2;
46            stateQueue.push(make_tuple(pos, pos, 0));
47            stateQueue.push(make_tuple(pos, pos, 1));
48        }
49
50        // Process states using backward induction
51        while (!stateQueue.empty()) {
52            auto currentState = stateQueue.front();
53            stateQueue.pop();
54          
55            int mousePos = get<0>(currentState);
56            int catPos = get<1>(currentState);
57            int turn = get<2>(currentState);
58            int currentResult = result[mousePos][catPos][turn];
59          
60            // Get all previous states that can lead to current state
61            for (auto& prevState : getPreviousStates(mouseGraph, catGraph, currentState, result)) {
62                int prevMousePos = get<0>(prevState);
63                int prevCatPos = get<1>(prevState);
64                int prevTurn = get<2>(prevState);
65              
66                // If previous turn player can achieve their winning result
67                if (prevTurn == currentResult - 1) {
68                    // Immediate win for the player (mouse wins if prevTurn=0 and result=1,
69                    // cat wins if prevTurn=1 and result=2)
70                    result[prevMousePos][prevCatPos][prevTurn] = currentResult;
71                    stateQueue.push(prevState);
72                } else {
73                    // Not a favorable outcome for the player, decrease degree
74                    degree[prevMousePos][prevCatPos][prevTurn]--;
75                  
76                    // If all moves lead to opponent's win, this player loses
77                    if (degree[prevMousePos][prevCatPos][prevTurn] == 0) {
78                        result[prevMousePos][prevCatPos][prevTurn] = currentResult;
79                        stateQueue.push(prevState);
80                    }
81                }
82            }
83        }
84
85        return result[mouseStart][catStart][0];  // Mouse moves first
86    }
87
88    /**
89     * Get all possible previous states that can lead to the current state
90     */
91    vector<tuple<int, int, int>> getPreviousStates(vector<vector<int>>& mouseGraph, 
92                                                   vector<vector<int>>& catGraph,
93                                                   tuple<int, int, int>& currentState,
94                                                   vector<vector<vector<int>>>& result) {
95        int mousePos = get<0>(currentState);
96        int catPos = get<1>(currentState);
97        int turn = get<2>(currentState);
98      
99        // Previous turn is opposite of current turn
100        int previousTurn = turn ^ 1;
101        vector<tuple<int, int, int>> previousStates;
102      
103        if (previousTurn == 1) {
104            // Previous turn was cat's turn, so cat moved to current position
105            for (int prevCatPos : catGraph[catPos]) {
106                // Only consider unprocessed states
107                if (result[mousePos][prevCatPos][1] == 0) {
108                    previousStates.push_back(make_tuple(mousePos, prevCatPos, previousTurn));
109                }
110            }
111        } else {
112            // Previous turn was mouse's turn, so mouse moved to current position
113            for (int prevMousePos : mouseGraph[mousePos]) {
114                // Only consider unprocessed states
115                if (result[prevMousePos][catPos][0] == 0) {
116                    previousStates.push_back(make_tuple(prevMousePos, catPos, 0));
117                }
118            }
119        }
120      
121        return previousStates;
122    }
123
124public:
125    /**
126     * Determine if the mouse can win the game
127     * @param grid: 2D grid representing the game board
128     * @param catJump: maximum jump distance for cat
129     * @param mouseJump: maximum jump distance for mouse
130     * @return: true if mouse can win, false otherwise
131     */
132    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
133        int rows = grid.size();
134        int cols = grid[0].length();
135        int catStartPos = 0, mouseStartPos = 0, foodPos = 0;
136      
137        // Build adjacency lists for mouse and cat movements
138        // Convert 2D grid to 1D representation: position = row * cols + col
139        vector<vector<int>> mouseGraph(rows * cols);
140        vector<vector<int>> catGraph(rows * cols);
141
142        // Process each cell in the grid
143        for (int row = 0; row < rows; row++) {
144            for (int col = 0; col < cols; col++) {
145                char cell = grid[row][col];
146              
147                // Skip walls
148                if (cell == '#') {
149                    continue;
150                }
151              
152                int currentPos = row * cols + col;
153              
154                // Record starting positions and food location
155                if (cell == 'C') {
156                    catStartPos = currentPos;
157                } else if (cell == 'M') {
158                    mouseStartPos = currentPos;
159                } else if (cell == 'F') {
160                    foodPos = currentPos;
161                }
162
163                // Build graph edges for all four directions
164                for (int dir = 0; dir < 4; ++dir) {
165                    // Add mouse edges (including staying in place with k=0)
166                    for (int jumpDist = 0; jumpDist <= mouseJump; jumpDist++) {
167                        int newRow = row + jumpDist * directions[dir];
168                        int newCol = col + jumpDist * directions[dir + 1];
169                      
170                        // Stop if out of bounds or hit a wall
171                        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || 
172                            grid[newRow][newCol] == '#') {
173                            break;
174                        }
175                      
176                        mouseGraph[currentPos].push_back(newRow * cols + newCol);
177                    }
178                  
179                    // Add cat edges (including staying in place with k=0)
180                    for (int jumpDist = 0; jumpDist <= catJump; jumpDist++) {
181                        int newRow = row + jumpDist * directions[dir];
182                        int newCol = col + jumpDist * directions[dir + 1];
183                      
184                        // Stop if out of bounds or hit a wall
185                        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || 
186                            grid[newRow][newCol] == '#') {
187                            break;
188                        }
189                      
190                        catGraph[currentPos].push_back(newRow * cols + newCol);
191                    }
192                }
193            }
194        }
195
196        // Mouse wins if the game outcome is 1
197        return calculateGameOutcome(mouseGraph, catGraph, mouseStartPos, catStartPos, foodPos) == 1;
198    }
199};
200
1// Direction vectors for moving up, right, down, left
2const DIRECTIONS: number[] = [-1, 0, 1, 0, -1];
3
4/**
5 * Calculate the game outcome using backward induction (minimax with DP)
6 * Returns: 1 if mouse wins, 2 if cat wins, 0 if draw
7 */
8function calculateGameOutcome(
9    mouseGraph: number[][],
10    catGraph: number[][],
11    mouseStart: number,
12    catStart: number,
13    foodPos: number
14): number {
15    const totalNodes = mouseGraph.length;
16  
17    // degree[mouse][cat][turn]: number of next states from current state
18    // turn: 0 = mouse's turn, 1 = cat's turn
19    const degree: number[][][] = Array(totalNodes)
20        .fill(null)
21        .map(() => Array(totalNodes)
22            .fill(null)
23            .map(() => Array(2).fill(0))
24        );
25  
26    // result[mouse][cat][turn]: game outcome from this state
27    // 0 = unknown, 1 = mouse wins, 2 = cat wins
28    const result: number[][][] = Array(totalNodes)
29        .fill(null)
30        .map(() => Array(totalNodes)
31            .fill(null)
32            .map(() => Array(2).fill(0))
33        );
34  
35    // Queue for BFS traversal of game states
36    const stateQueue: [number, number, number][] = [];
37  
38    // Initialize degree counts for each state
39    for (let mousePos = 0; mousePos < totalNodes; mousePos++) {
40        for (let catPos = 0; catPos < totalNodes; catPos++) {
41            degree[mousePos][catPos][0] = mouseGraph[mousePos].length;  // Mouse's turn
42            degree[mousePos][catPos][1] = catGraph[catPos].length;      // Cat's turn
43        }
44    }
45  
46    // Initialize terminal states and add them to queue
47    for (let pos = 0; pos < totalNodes; pos++) {
48        // Mouse reaches food (mouse wins) - cat's turn doesn't matter
49        result[foodPos][pos][1] = 1;
50        stateQueue.push([foodPos, pos, 1]);
51      
52        // Cat reaches food (cat wins) - mouse's turn
53        result[pos][foodPos][0] = 2;
54        stateQueue.push([pos, foodPos, 0]);
55      
56        // Cat catches mouse (cat wins) - both turns
57        result[pos][pos][0] = 2;
58        result[pos][pos][1] = 2;
59        stateQueue.push([pos, pos, 0]);
60        stateQueue.push([pos, pos, 1]);
61    }
62  
63    // Process states using backward induction
64    while (stateQueue.length > 0) {
65        const currentState = stateQueue.shift()!;
66        const [mousePos, catPos, turn] = currentState;
67        const currentResult = result[mousePos][catPos][turn];
68      
69        // Get all previous states that can lead to current state
70        const previousStates = getPreviousStates(mouseGraph, catGraph, currentState, result);
71      
72        for (const prevState of previousStates) {
73            const [prevMousePos, prevCatPos, prevTurn] = prevState;
74          
75            // If previous turn player can achieve their winning result
76            if (prevTurn === currentResult - 1) {
77                // Immediate win for the player (mouse wins if prevTurn=0 and result=1,
78                // cat wins if prevTurn=1 and result=2)
79                result[prevMousePos][prevCatPos][prevTurn] = currentResult;
80                stateQueue.push(prevState);
81            } else {
82                // Not a favorable outcome for the player, decrease degree
83                degree[prevMousePos][prevCatPos][prevTurn]--;
84              
85                // If all moves lead to opponent's win, this player loses
86                if (degree[prevMousePos][prevCatPos][prevTurn] === 0) {
87                    result[prevMousePos][prevCatPos][prevTurn] = currentResult;
88                    stateQueue.push(prevState);
89                }
90            }
91        }
92    }
93  
94    return result[mouseStart][catStart][0];  // Mouse moves first
95}
96
97/**
98 * Get all possible previous states that can lead to the current state
99 */
100function getPreviousStates(
101    mouseGraph: number[][],
102    catGraph: number[][],
103    currentState: [number, number, number],
104    result: number[][][]
105): [number, number, number][] {
106    const [mousePos, catPos, turn] = currentState;
107  
108    // Previous turn is opposite of current turn
109    const previousTurn = turn ^ 1;
110    const previousStates: [number, number, number][] = [];
111  
112    if (previousTurn === 1) {
113        // Previous turn was cat's turn, so cat moved to current position
114        for (const prevCatPos of catGraph[catPos]) {
115            // Only consider unprocessed states
116            if (result[mousePos][prevCatPos][1] === 0) {
117                previousStates.push([mousePos, prevCatPos, previousTurn]);
118            }
119        }
120    } else {
121        // Previous turn was mouse's turn, so mouse moved to current position
122        for (const prevMousePos of mouseGraph[mousePos]) {
123            // Only consider unprocessed states
124            if (result[prevMousePos][catPos][0] === 0) {
125                previousStates.push([prevMousePos, catPos, 0]);
126            }
127        }
128    }
129  
130    return previousStates;
131}
132
133/**
134 * Determine if the mouse can win the game
135 * @param grid - 2D grid representing the game board
136 * @param catJump - maximum jump distance for cat
137 * @param mouseJump - maximum jump distance for mouse
138 * @returns true if mouse can win, false otherwise
139 */
140function canMouseWin(grid: string[], catJump: number, mouseJump: number): boolean {
141    const rows = grid.length;
142    const cols = grid[0].length;
143    let catStartPos = 0;
144    let mouseStartPos = 0;
145    let foodPos = 0;
146  
147    // Build adjacency lists for mouse and cat movements
148    // Convert 2D grid to 1D representation: position = row * cols + col
149    const mouseGraph: number[][] = Array(rows * cols).fill(null).map(() => []);
150    const catGraph: number[][] = Array(rows * cols).fill(null).map(() => []);
151  
152    // Process each cell in the grid
153    for (let row = 0; row < rows; row++) {
154        for (let col = 0; col < cols; col++) {
155            const cell = grid[row][col];
156          
157            // Skip walls
158            if (cell === '#') {
159                continue;
160            }
161          
162            const currentPos = row * cols + col;
163          
164            // Record starting positions and food location
165            if (cell === 'C') {
166                catStartPos = currentPos;
167            } else if (cell === 'M') {
168                mouseStartPos = currentPos;
169            } else if (cell === 'F') {
170                foodPos = currentPos;
171            }
172          
173            // Build graph edges for all four directions
174            for (let dir = 0; dir < 4; dir++) {
175                // Add mouse edges (including staying in place with jumpDist=0)
176                for (let jumpDist = 0; jumpDist <= mouseJump; jumpDist++) {
177                    const newRow = row + jumpDist * DIRECTIONS[dir];
178                    const newCol = col + jumpDist * DIRECTIONS[dir + 1];
179                  
180                    // Stop if out of bounds or hit a wall
181                    if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols ||
182                        grid[newRow][newCol] === '#') {
183                        break;
184                    }
185                  
186                    mouseGraph[currentPos].push(newRow * cols + newCol);
187                }
188              
189                // Add cat edges (including staying in place with jumpDist=0)
190                for (let jumpDist = 0; jumpDist <= catJump; jumpDist++) {
191                    const newRow = row + jumpDist * DIRECTIONS[dir];
192                    const newCol = col + jumpDist * DIRECTIONS[dir + 1];
193                  
194                    // Stop if out of bounds or hit a wall
195                    if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols ||
196                        grid[newRow][newCol] === '#') {
197                        break;
198                    }
199                  
200                    catGraph[currentPos].push(newRow * cols + newCol);
201                }
202            }
203        }
204    }
205  
206    // Mouse wins if the game outcome is 1
207    return calculateGameOutcome(mouseGraph, catGraph, mouseStartPos, catStartPos, foodPos) === 1;
208}
209

Time and Space Complexity

Time Complexity: O(n^2 * m^2 * (catJump + mouseJump))

The time complexity breaks down as follows:

  • Building the graph: O(n * m * (catJump + mouseJump)) - For each cell in the grid, we explore up to catJump + mouseJump positions in 4 directions
  • BFS traversal: O((n * m)^2 * 2) - We have states represented as (mouse_position, cat_position, turn), where:
    • Mouse can be in any of n * m positions
    • Cat can be in any of n * m positions
    • Turn can be 0 or 1
    • Total states: (n * m) * (n * m) * 2 = O(n^2 * m^2)
  • For each state, we process its previous states which is bounded by the degree (number of edges), giving us O(n * m) work per state in the worst case
  • Overall: O(n * m * (catJump + mouseJump) + n^2 * m^2) = O(n^2 * m^2 * max(1, (catJump + mouseJump)/(n*m)))

Since typically catJump and mouseJump are constants or small relative to grid size, the dominant term is O(n^2 * m^2).

Space Complexity: O(n^2 * m^2)

The space complexity consists of:

  • Graph adjacency lists g_mouse and g_cat: O(n * m * max(catJump, mouseJump)) - Each cell can connect to at most 4 * max(catJump, mouseJump) other cells
  • degree array: O((n * m)^2 * 2) = O(n^2 * m^2) - Stores degree for each state
  • ans array: O((n * m)^2 * 2) = O(n^2 * m^2) - Stores result for each state
  • Queue q: O(n^2 * m^2) in worst case when all states are enqueued

The dominant space requirement is O(n^2 * m^2) from the state arrays.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Turn Encoding Leading to Wrong Win Condition Mapping

One of the most common pitfalls in this solution is confusing the turn encoding with the winner encoding, which can lead to incorrect game outcome determination.

The Problem: The code uses:

  • Turn encoding: 0 for mouse's turn, 1 for cat's turn
  • Result encoding: 1 for mouse wins, 2 for cat wins

The critical line that often causes confusion is:

if prev_turn == current_result - 1:

This condition checks if the previous player can force a win. The logic is:

  • If current_result = 1 (mouse wins) and prev_turn = 0 (mouse's turn), then 0 == 1 - 1 ✓
  • If current_result = 2 (cat wins) and prev_turn = 1 (cat's turn), then 1 == 2 - 1 ✓

Why It's Easy to Get Wrong: Developers often mistakenly think the turn number should directly correspond to the winner number, leading to incorrect implementations like:

# WRONG: This doesn't correctly identify when a player can force a win
if prev_turn == current_result:  # Incorrect logic

Solution: Always remember that the encoding offset exists: mouse (turn 0) wins with result 1, cat (turn 1) wins with result 2. Document this clearly and consider using named constants:

# Better approach with clear constants
MOUSE_TURN = 0
CAT_TURN = 1
MOUSE_WINS = 1
CAT_WINS = 2

# Then the condition becomes clearer:
if prev_turn == current_result - 1:
    # Previous player can force this winning outcome

2. Forgetting to Handle the "Stay in Place" Move

The Problem: The game rules allow players to jump 0 distance (stay in place), but it's easy to accidentally start the jump range from 1:

# WRONG: Missing the stay-in-place option
for jump_dist in range(1, mouseJump + 1):  # Starts from 1, missing 0
    # ...

Why This Matters: Staying in place can be a crucial strategic move. For example:

  • Mouse might need to stay put to force cat into a bad position
  • Cat might stay to guard the food location

Solution: Always include 0 in the jump range:

# CORRECT: Include 0 to allow staying in place
for jump_dist in range(mouseJump + 1):  # Starts from 0
    new_row, new_col = row_idx + jump_dist * dx, col_idx + jump_dist * dy
    # ...

3. Duplicate States in Adjacency Lists

The Problem: When building the movement graph, the current implementation can add duplicate positions to the adjacency lists. For example, a player at position (1,1) can reach (1,1) by jumping 0 in any of the 4 directions, potentially adding the same position 4 times.

Why It Causes Issues:

  • Inflates the degree count, making it harder for states to reach degree 0
  • Can cause incorrect game outcome calculations
  • Wastes computational resources

Solution: Use a set to track unique positions before converting to a list:

# Build adjacency lists without duplicates
for row_idx, row in enumerate(grid):
    for col_idx, cell in enumerate(row):
        if cell == "#":
            continue
      
        current_pos = row_idx * cols + col_idx
        mouse_moves = set()  # Use set to avoid duplicates
        cat_moves = set()
      
        for dx, dy in pairwise(directions):
            for jump_dist in range(mouseJump + 1):
                new_row, new_col = row_idx + jump_dist * dx, col_idx + jump_dist * dy
                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != "#":
                    mouse_moves.add(new_row * cols + new_col)
                else:
                    break
          
            for jump_dist in range(catJump + 1):
                new_row, new_col = row_idx + jump_dist * dx, col_idx + jump_dist * dy
                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != "#":
                    cat_moves.add(new_row * cols + new_col)
                else:
                    break
      
        mouse_graph[current_pos] = list(mouse_moves)
        cat_graph[current_pos] = list(cat_moves)

This ensures each reachable position appears exactly once in the adjacency list, leading to correct degree counting and game outcome calculation.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More