1728. Cat and Mouse II

HardGraphTopological SortMemoizationArrayMathDynamic ProgrammingGame TheoryMatrix

Problem Description

In this game, there is a cat and a mouse located on a grid. The grid includes walls, floors, and a food item. The mouse and the cat each take turns moving toward the food, and they can jump a certain number of grid spaces per turn. The mouse gets the first move. They can move in any direction but cannot pass through walls or leave the grid boundary. Moreover, the mouse is allowed to jump over the cat.

The game concludes in four scenarios:

If the cat lands on the same space as the mouse, the cat wins.
If the cat lands on the food first, the cat wins.
If the mouse reaches the food, the mouse wins.
The cat wins if the mouse has not reached the food within 1000 turns.

The objective is to determine if the mouse can win given that both the cat and mouse play optimally. We are to return true if the mouse can win under these conditions or false otherwise.

Intuition

To solve this problem, we need to consider all possible moves of both the mouse and the cat. This is a classic example of a game theory problem where we use minimax strategy or dynamic programming to simulate each player's optimal moves.

The intuition behind the solution is to use a depth-first search (DFS) approach with memoization to avoid recomputing the game state's result over and over again. By tracking each player's move and position as well as the turn number, we can recursively explore all possible moves for both players.

To manage the complexity of the game states, we hash the 2D grid positions into a single integer to represent each unique position. The memoization will then store these states and speed up the process by retrieving the outcome of previously visited states.

We use an dp function where dp(cat, mouse, turn) tells us if the mouse can win given that it's turn number turn, the cat is at position cat, and the mouse is at position mouse. Since the mouse moves first, the turn number starting from 0 indicates it's the mouse's turn, otherwise, it's the cat's turn.

During each turn, we explore all possible jump distances (from 0 up to the maximum allowed jumps) for the current player in all four directions unless a wall is hit or the grid boundary is reached.

For the mouse's turn:

If the mouse reaches the food, the mouse wins and we return true.
If the mouse cannot win in any possible move, the mouse loses and we return false.

For the cat's turn:

If the cat reaches the food or catches the mouse, the mouse loses and we return false.
If the cat cannot capture the mouse or reach the food in its move, and therefore the mouse wins all subsequent moves, the mouse wins, so we return true.

Finally, if after a certain number of turns neither player wins, we terminate the search as the cat wins by default, ending with a false. We use memoization to recall states that have already been computed, making the solution feasible within the time constraints.

This approach ensures that we simulate every possible game scenario within the constraints of the game, rigorously checking if there exists a winning strategy for the mouse under optimal play conditions.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Solution Approach

The solution uses several key algorithms and patterns:

Depth-First Search (DFS): This recurses through all possible game states (combinations of positions for Cat and Mouse and the number of turns).
Memoization: Implemented using Python's functools.lru_cache decorator, which caches the outcome of the DFS so that the same state is not recalculated unnecessarily.
State Hashing: Because the game state involves both positions and the number of turns, the positions of the Cat and Mouse are hashed into single integers to simplify state management.
Turn-based Logic: The function dp checks whose turn it is based on the turn number (turn % 2). On even turns, it's the Mouse's turn, and on odd turns, it's the Cat's turn.

The dp function is the core of our solution, where the parameters cat, mouse, and turn represent the game's current state.

For the Mouse's turn, we iterate over all available directions (left, right, up, down) and try all possible jumps from 0 to mouseJump. During this process, we check:
- If we hit a wall (grid[x][y] == "#") or go out of bounds, we break from the loop, as the Mouse cannot pass through walls.
- If the Mouse finds the food (grid[x][y] == "F"), the function immediately returns true.
- If none of the positions result in the Mouse winning, the function returns false after checking all possibilities.
For the Cat's turn, similar logic is applied. We iterate through all possible positions the Cat can jump to:
- The Cat wins if it reaches the food or catches the Mouse; hence in these cases, the function returns false as the mouse cannot win.
- If there is any position where the Cat move does not lead to the Mouse's immediate loss, we continue exploring.

The algorithm will recursively call dp until a base case is met (food is reached, or the cat catches the mouse). The recursion depth is bounded by the maximum number of floors times 2, which represents all reachable states in the game without any repetition.

Data structures used:

Grid Representation: The grid is a list of strings where each string represents a row in the grid.
Directions Array: Used to iterate over possible moves (left, right, up, down).
Memoization Cache: Utilizes Python's built-in caching mechanism to store previously calculated game states.

The solution concludes by initiating the DFS with the initial positions of the Cat and Mouse and starting at turn 0. The return value of dp(cat, mouse, 0) provides the final outcome of whether the Mouse can win if both Cat and Mouse play optimally.

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

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Example Walkthrough

Let's walk through a simplified example to illustrate the solution approach. Assume our grid is a 3x3 matrix and looks like this, where 'C' is the cat, 'M' is the mouse, 'F' is the food, '.' are floors, and '#' are walls:

1C.M
2.#.
3..F

Here, the cat can jump 1 space at a time (max), and the mouse can also jump just 1 space at a time. Let's analyze a few turns with the cat starting at position (0,0) and the mouse at position (0,2).

Turn 0 (Mouse's turn)

The mouse can move to either (1,2) or (0,1). However, moving to (0,1) is not optimal since it brings the mouse closer to the cat. Thus, the optimal move for the mouse is to (1,2).

Turn 1 (Cat's turn)

The cat can move to (0,1) or (1,0), but moving to (1,0) will not be beneficial since it moves the cat further from both the mouse and the food. Thus, the cat moves to (0,1).

New grid state:

1C..
2.M.
3..F

Turn 2 (Mouse's turn)

The mouse is now at (1,2) and has to decide between moving closer to the food or away from it. Since the objective is to win, it moves to (2,2), where the food is located.

1C..
2.#.
3..M

Now the mouse has reached the 'F' on the grid, so according to the rules, the mouse wins.

Solution Approach In Action

Now, let's map this scenario into our solution approach described above. The dp function is called with the initial positions of cat and mouse, and a turn number of 0.

The DFS explores all of the mouse's possible moves, and finds that moving to (1,2) is the only move that potentially leads to a win.
With the new game state, the DFS is called for the cat's turn, evaluating the cat's possible moves.
On Turn 2, when the dp function is called, it sees that the mouse can move directly to the food, thus returning true.
Since the call to dp with the initial state led to a mouse victory, we know that, playing optimally, the mouse can win in this scenario.

Using the above solution approach with memoization and state hashing, the function ensures that each state is computed only once, saving time in larger grids with more complex scenarios. Memoization is crucial in avoiding recomputation of game states, and the recursiveness of DFS allows us to explore each possible move to determine the optimal path to victory for the mouse.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def can_mouse_win(self, grid: List[str], cat_jump: int, mouse_jump: int) -> bool:
5        # Direction vectors for up, right, down, left movements
6        directions = [0, 1, 0, -1, 0]
7        m, n = len(grid), len(grid[0])
8        num_floors = 0  # Number of non-wall cells
9        cat_pos = 0     # Cat's starting position
10        mouse_pos = 0   # Mouse's starting position
11
12        # Helper function to convert 2D position to a unique 1D position
13        def hash_position(i: int, j: int) -> int:
14            return i * n + j
15
16        # Preprocess the grid to count non-wall cells and find cat and mouse positions
17        for i in range(m):
18            for j in range(n):
19                if grid[i][j] != '#':  # Count non-wall spaces
20                    num_floors += 1
21                if grid[i][j] == 'C':  # Find the cat's starting position
22                    cat_pos = hash_position(i, j)
23                elif grid[i][j] == 'M':  # Find the mouse's starting position
24                    mouse_pos = hash_position(i, j)
25
26        # Define the main DP function using memoization to check if mouse can win
27        # The state is defined by the cat's position, the mouse's position, and the turn number
28        @lru_cache(None)
29        def dp(cat: int, mouse: int, turn: int) -> bool:
30            # Base case: If all possible moves have been searched without a win, return False
31            if turn == num_floors * 2:
32                return False
33
34            # Mouse's turn
35            if turn % 2 == 0:
36                i, j = divmod(mouse, n)
37                for k in range(4):  # Each direction
38                    for jump in range(mouse_jump + 1):  # Possible jump lengths
39                        x, y = i + directions[k] * jump, j + directions[k + 1] * jump
40                        if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '#':
41                            break  # Out of bounds or hit a wall
42                        if grid[x][y] == 'F':
43                            return True  # Mouse wins as it reaches the food
44                        if dp(cat, hash_position(x, y), turn + 1):
45                            return True  # Move to next turn
46                return False  # No move leads to a win, so mouse loses
47
48            # Cat's turn
49            else:
50                i, j = divmod(cat, n)
51                for k in range(4):  # Each direction
52                    for jump in range(cat_jump + 1):  # Possible jump lengths
53                        x, y = i + directions[k] * jump, j + directions[k + 1] * jump
54                        if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '#':
55                            break  # Out of bounds or hit a wall
56                        if grid[x][y] == 'F' or hash_position(x, y) == mouse:
57                            return False  # Cat wins (mouse loses) if it reaches the food or catches the mouse
58                        if not dp(hash_position(x, y), mouse, turn + 1):
59                            return False  # Move to next turn
60                return True  # No move leads to a loss, so mouse wins
61
62        # Initial call to the DP function to decide if the mouse can win
63        return dp(cat_pos, mouse_pos, 0)
64

1import java.util.List;
2import java.util.Arrays;
3
4public class Solution {
5    // Using memoization to cache results and avoid recomputing them
6    private Boolean[][][] memo;
7  
8    // Directions to move on the grid
9    private final int[] directions = {0, 1, 0, -1, 0};
10
11    // Main method to check if the mouse can win
12    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
13        int m = grid.length;
14        int n = grid[0].length();
15        int numFloors = 0; // Number of non-wall cells
16        int catPos = 0; // Cat's starting position (in 1D)
17        int mousePos = 0; // Mouse's starting position (in 1D)
18
19        // Preprocessing the grid to count non-wall cells and find cat and mouse positions
20        for (int i = 0; i < m; i++) {
21            for (int j = 0; j < n; j++) {
22                if (grid[i].charAt(j) != '#') numFloors++;
23                if (grid[i].charAt(j) == 'C') catPos = i * n + j;
24                if (grid[i].charAt(j) == 'M') mousePos = i * n + j;
25            }
26        }
27
28        // Initialize memoization cache with null values
29        memo = new Boolean[m * n][m * n][numFloors * 2];
30
31        // Initial call to the helper method, starting with turn 0
32        return canWin(m, n, catPos, mousePos, 0, mouseJump, catJump);
33    }
34
35    // Helper method to check recursively if the mouse can win
36    private boolean canWin(int m, int n, int cat, int mouse, int turn, int mouseJump, int catJump) {
37        if (turn == m * n * 2) return false; // No one wins if all cells have been visited twice
38        if (memo[cat][mouse][turn] != null) return memo[cat][mouse][turn]; // Check if result is already computed
39
40        boolean mouseTurn = (turn % 2 == 0);
41        int[] agentPos = (mouseTurn ? divmod(mouse, n) : divmod(cat, n));
42        int jump = (mouseTurn ? mouseJump : catJump);
43
44        for (int k = 0; k < 4; k++) { // Try all directions
45            for (int j = 1; j <= jump; j++) { // Try all jump lengths
46                int x = agentPos[0] + directions[k] * j;
47                int y = agentPos[1] + directions[k + 1] * j;
48                if (x < 0 || x >= m || y < 0 || y >= n || grid[x].charAt(y) == '#') break; // Out of bounds or wall
49
50                // Mouse's turn checks
51                if (mouseTurn && grid[x].charAt(y) == 'F') return memo[cat][mouse][turn] = true; // Mouse wins by finding food
52                if (mouseTurn && canWin(m, n, cat, x * n + y, turn + 1, mouseJump, catJump)) return memo[cat][mouse][turn] = true; // Mouse can win in next move
53              
54                // Cat's turn checks
55                if (!mouseTurn && (grid[x].charAt(y) == 'F' || x * n + y == mouse)) return memo[cat][mouse][turn] = false; // Cat wins by finding food or catching the mouse
56                if (!mouseTurn && !canWin(m, n, x * n + y, mouse, turn + 1, mouseJump, catJump)) return memo[cat][mouse][turn] = false; // Cat can win in next move
57            }
58        }
59
60        // If we reached here, no jump leads to win/loss for the current agent
61        return memo[cat][mouse][turn] = mouseTurn ? false : true;
62    }
63
64    // Helper method to convert 2D indices to a 1D index
65    private int hashPosition(int i, int j, int n) {
66        return i * n + j;
67    }
68  
69    // Helper method to convert back from 1D index to 2D indices
70    private int[] divmod(int val, int n) {
71        return new int[]{val / n, val % n};
72    }
73}
74

1#include <vector>
2#include <string>
3#include <functional>
4#include <unordered_map>
5
6using namespace std;
7
8class Solution {
9public:
10    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
11        // Direction vectors for up, right, down, left movements
12        vector<int> directions = {0, 1, 0, -1, 0};
13        int m = grid.size();
14        int n = grid[0].size();
15        int numFloors = 0;   // Number of non-wall cells
16        int catPos = 0;      // Cat's starting position
17        int mousePos = 0;    // Mouse's starting position
18
19        // Lambda to convert 2D position to 1D
20        auto hashPosition = [n](int i, int j) {
21            return i * n + j;
22        };
23
24        // Preprocess the grid to count non-wall cells and find cat and mouse positions
25        for (int i = 0; i < m; ++i) {
26            for (int j = 0; j < n; ++j) {
27                if (grid[i][j] != '#') {  // Count non-wall spaces
28                    ++numFloors;
29                }
30                if (grid[i][j] == 'C') {  // Find the cat's starting position
31                    catPos = hashPosition(i, j);
32                } else if (grid[i][j] == 'M') {  // Find the mouse's starting position
33                    mousePos = hashPosition(i, j);
34                }
35            }
36        }
37
38        // Memoization map
39        unordered_map<int, bool> memo;
40
41        // Recursive DP function to check if mouse can win
42        // The state is compressed into a single integer (passed as the argument 'state')
43        function<bool(int, int, int)> dp = [&](int cat, int mouse, int turn) -> bool {
44            // Compress the state into one integer (cat's position, mouse's position, turn)
45            int state = (cat << 16) | (mouse << 8) | turn;
46            if (memo.count(state)) {
47                return memo[state];
48            }
49
50            // Base case: If all possible moves have been searched without a win, return false
51            if (turn == numFloors * 2) {
52                return memo[state] = false;
53            }
54
55            // Mouse's turn
56            if (turn % 2 == 0) {
57                int i = mouse / n;
58                int j = mouse % n;
59                for (int k = 0; k < 4; ++k) { // Each direction
60                    for (int jump = 0; jump <= mouseJump; ++jump) { // Possible jump lengths
61                        int x = i + directions[k] * jump;
62                        int y = j + directions[k + 1] * jump;
63                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
64                            break; // Out of bounds or hit a wall
65                        }
66                        if (grid[x][y] == 'F') {
67                            return memo[state] = true; // Mouse wins as it reaches the food
68                        }
69                        if (dp(cat, hashPosition(x, y), turn + 1)) {
70                            return memo[state] = true; // Move to the next turn
71                        }
72                    }
73                }
74                return memo[state] = false;  // No move leads to a win, so mouse loses
75            }
76            // Cat's turn
77            else {
78                int i = cat / n;
79                int j = cat % n;
80                for (int k = 0; k < 4; ++k) { // Each direction
81                    for (int jump = 0; jump <= catJump; ++jump) { // Possible jump lengths
82                        int x = i + directions[k] * jump;
83                        int y = j + directions[k + 1] * jump;
84                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
85                            break; // Out of bounds or hit a wall
86                        }
87                        if (grid[x][y] == 'F' || hashPosition(x, y) == mouse) {
88                            return memo[state] = false;  // Cat wins if it reaches the food or catches the mouse
89                        }
90                        if (!dp(hashPosition(x, y), mouse, turn + 1)) {
91                            return memo[state] = false;  // Move to the next turn
92                        }
93                    }
94                }
95                return memo[state] = true;  // No move leads to a loss, so mouse wins
96            }
97        };
98
99        // Initial call to the DP function to decide if the mouse can win
100        return dp(catPos, mousePos, 0);
101    }
102};
103

1type Grid = string[];
2type Position = number;  // Type alias for representing positions
3
4// Direction vectors for up, right, down, left movements
5const directions: number[] = [0, 1, 0, -1, 0];
6
7// Converts a 2D position to a unique 1D position
8function hashPosition(i: number, j: number, n: number): Position {
9    return i * n + j;
10}
11
12// Main function to check if the mouse can win
13function canMouseWin(grid: Grid, catJump: number, mouseJump: number): boolean {
14    const m: number = grid.length;
15    const n: number = grid[0].length;
16    let numFloors: number = 0;  // Number of non-wall cells
17    let catPos: Position = 0;   // Cat's starting position
18    let mousePos: Position = 0; // Mouse's starting position
19
20    // Preprocess the grid to count non-wall cells and find cat and mouse positions
21    for (let i = 0; i < m; i++) {
22        for (let j = 0; j < n; j++) {
23            if (grid[i][j] !== '#') numFloors++;
24            if (grid[i][j] === 'C') catPos = hashPosition(i, j, n);
25            else if (grid[i][j] === 'M') mousePos = hashPosition(i, j, n);
26        }
27    }
28
29    // Memoization cache
30    const memo: Map<string, boolean> = new Map<string, boolean>();
31
32    // Dynamic programming function to determine the game state
33    function dp(cat: Position, mouse: Position, turn: number): boolean {
34        const key: string = `${cat},${mouse},${turn}`;
35        if (memo.has(key)) return memo.get(key)!;
36
37        // Base case: If all possible moves have been searched without a win, return false
38        if (turn === numFloors * 2) {
39            memo.set(key, false);
40            return false;
41        }
42
43        let result: boolean = false;
44
45        // Mouse's turn
46        if (turn % 2 === 0) {
47            let [i, j] = [Math.floor(mouse / n), mouse % n];
48            for (let k = 0; k < 4; k++) {  // Each direction
49                for (let jump = 0; jump <= mouseJump; jump++) {  // Possible jump lengths
50                    let x = i + directions[k] * jump;
51                    let y = j + directions[k + 1] * jump;
52                    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] === '#') break;  // Out of bounds or hit a wall
53                    if (grid[x][y] === 'F') {
54                        memo.set(key, true);
55                        return true;  // Mouse wins as it reaches the food
56                    }
57                    result = dp(cat, hashPosition(x, y, n), turn + 1);
58                    if (result) {
59                        memo.set(key, true);
60                        return true;  // Mouse finds a winning move
61                    }
62                }
63            }
64        }
65        // Cat's turn
66        else {
67            let [i, j] = [Math.floor(cat / n), cat % n];
68            for (let k = 0; k < 4; k++) {  // Each direction
69                for (let jump = 0; jump <= catJump; jump++) {  // Possible jump lengths
70                    let x = i + directions[k] * jump;
71                    let y = j + directions[k + 1] * jump;
72                    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] === '#') break;  // Out of bounds or hit a wall
73                    if (grid[x][y] === 'F' || hashPosition(x, y, n) === mouse) {
74                        memo.set(key, false);
75                        return false;  // Cat wins if it reaches the food or catches the mouse
76                    }
77                    result = !dp(hashPosition(x, y, n), mouse, turn + 1);
78                    if (result) {
79                        memo.set(key, true);
80                        return true;  // Cat finds a move that does not lead to a loss
81                    }
82                }
83            }
84        }
85      
86        memo.set(key, result);
87        return result;
88    }
89
90    // Initial call to the DP function to decide if the mouse can win
91    return dp(catPos, mousePos, 0);
92}
93

Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Heap sortMerge sortInsertion sortQuick sort

I don’t know

Time and Space Complexity

The given Python code solves a problem where the objective is to determine if the mouse can win, provided it and the cat take turns to jump on a grid with the goal to reach the food first, or for the cat to catch the mouse.

Time Complexity

The time complexity of this code is determined by the number of states that the dynamic programming dp function needs to compute and the number of iterations needed for each turn.

The main components that contribute to the time complexity are:

The grid size m * n, which denotes the potential places the cat or the mouse can be.
The maximum number of turns nFloors * 2, which is the stopping condition for the recursion and ensures that the function eventually terminates.
The jumps per turn for the mouse and the cat, which are up to mouseJump + 1 and catJump + 1 respectively, times the four possible directions.

Since each position is computed only once due to memoization (functools.lru_cache), we need to consider the number of unique states. The number of unique states for the dp function would be m * n positions for the mouse times m * n positions for the cat times nFloors * 2 turns.

Therefore, the time complexity is O((m*n)^2 * nFloors * 2 * (mouseJump + 1) * (catJump + 1) * 4), which simplifies to O(m^2 * n^2 * (mouseJump + catJump)) since m * n is proportional to nFloors and the constant 2 and 4 are negligible for big-O notation.

Space Complexity

As for the space complexity:

Memoization uses a cache that will store each computed state; hence, the space complexity is similar to the time complexity in terms of the number of unique states. Thus, the space complexity is O((m*n)^2 * nFloors * 2).
The recursive nature of the solution implies a call stack depth that could go up to nFloors * 2. However, even with memoization, this doesn't affect the space complexity asymptotically, as the cache dominates the space usage.

The resulting space complexity is O(m^2 * n^2 * nFloors), which simplifies to O((m*n)^2) since nFloors is within the same order of magnitude as m * n.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1728. Cat and Mouse II

Problem Description

Intuition

Solution Approach

Example Walkthrough

Turn 0 (Mouse's turn)

Turn 1 (Cat's turn)

Turn 2 (Mouse's turn)

Solution Approach In Action

Solution Implementation

Time and Space Complexity