1728. Cat and Mouse II - Leetcode Solution

Problem Description

The Cat and Mouse II problem involves simulating a two-player game on a grid. The grid is represented as a 2D array of characters, where each cell can be:

'#': a wall (cannot be passed)
'.': an empty cell (can be moved into)
'C': the starting position of the cat
'M': the starting position of the mouse
'F': the food

The mouse and the cat take turns to move. The mouse moves first. On each turn, a player can move up to jump steps in any of the four cardinal directions (up, down, left, right), but cannot move through walls or outside the grid. The mouse has mouseJump steps per turn, and the cat has catJump steps per turn.

The objective is for the mouse to reach the food before being caught by the cat, or before the cat reaches the food. The cat catches the mouse if they are in the same cell after a move. The mouse wins if it reaches the food first. The cat wins if it catches the mouse or reaches the food first. If the game exceeds 1000 turns, the cat wins by default.

The task is to determine if the mouse can win, assuming both players play optimally.

Thought Process

At first glance, this problem looks like a classic two-player game with perfect information, much like chess or tic-tac-toe, but on a grid. The main challenge is simulating all possible moves for both players, considering their jump limits and the obstacles (walls).

A brute-force approach would try every possible sequence of moves, but this quickly becomes infeasible due to the exponential number of game states. Instead, we realize this is a minimax problem: the mouse tries to maximize its chances of winning, while the cat tries to minimize them.

We need to model the game as a series of states (positions of mouse and cat, whose turn it is, and turn count), and determine from each state whether the mouse can force a win. To avoid re-computation, we should cache (memoize) the results of previously computed states.

The main conceptual leap is recognizing that this is a game theory problem with recursive state evaluation and memoization.

Solution Approach

Let's break down the solution step by step:

Parse the Grid:
- Locate the positions of the mouse, cat, and food.
Model the Game State:
- Represent the state as a tuple: (mouse_x, mouse_y, cat_x, cat_y, turn_number, is_mouse_turn).
- We need to keep track of whose turn it is, and how many turns have passed.
Recursive Minimax with Memoization:
- For each state, recursively simulate all possible moves for the current player (within jump limits and not through walls).
- If the mouse reaches the food, return True (mouse wins).
- If the cat catches the mouse or reaches the food, return False (cat wins).
- If the turn count exceeds 1000, return False (cat wins by default).
- Memoize the result for each state to avoid recomputation.
Move Generation:
- For each direction, try all possible jump lengths from 1 up to the player's allowed jump.
- Stop if you hit a wall or the edge of the grid.
- Include the option to stay in place (jump 0).
Game Tree Pruning:
- If the current player can force a win in any move, return that outcome immediately (pruning unnecessary branches).
Memoization:
- Use a hash map (dictionary) keyed by the state tuple for fast lookups (O(1)).

This approach ensures that each unique game state is only computed once, and that optimal play is simulated for both players.

Example Walkthrough

Sample Input:

      grid = [
        "M.C..",
        "##.##",
        "..F.."
      ]
      catJump = 1
      mouseJump = 2

Step-by-step:

Initial Positions:
- Mouse: (0,0)
- Cat: (0,2)
- Food: (2,2)
Turn 1 (Mouse):
- Mouse can move up to 2 steps in any direction, avoiding walls.
- Possible moves: (0,1), (0,2), (1,0), (2,0), etc., but some are blocked by walls.
Turn 2 (Cat):
- Cat can move 1 step in any direction, but must avoid walls.
- Possible moves: (0,1), (1,2), etc.
Continue:
- At each turn, recursively simulate all valid moves for the current player.
- If the mouse reaches (2,2) before the cat, mouse wins. If the cat catches the mouse or gets to (2,2) first, cat wins.
Memoization:
- States already computed are cached, so if the game revisits them, the result is returned instantly.

Result: The function returns whether the mouse can win, assuming both play optimally.

Time and Space Complexity

Brute-Force:

Exponential time: At each turn, the player can have up to O(N^2) possible moves (where N is the grid size), and the game can last up to 1000 turns.
So, total states: O((N^2)^2 * 1000 * 2) = O(N^4 * 1000), but without memoization, the number of recursive calls is much higher due to repeated states.

Optimized (with Memoization):

Each state is defined by (mouse position, cat position, turn number, whose turn). There are at most N^2 positions for each, 1000 turns, and 2 players.
So, total unique states = O(N^4 * 1000 * 2).
Each state is computed once, and each move takes O(1) time (since jumps are bounded).
Time Complexity: O(N^4 * 1000 * 2) = O(N^4 * 1000)
Space Complexity: O(N^4 * 1000) for the memoization table.

In practice, the constraints on N (grid size) and jump values keep the solution efficient.

Summary

The Cat and Mouse II problem is a classic example of a two-player perfect information game that can be solved using recursive minimax with memoization. By modeling each unique state and caching results, we avoid redundant computation and ensure an optimal solution. The key insight is recognizing the structure of the game and leveraging dynamic programming to evaluate game outcomes efficiently. This approach ensures the mouse's victory can be predicted accurately, even with complex movement rules and obstacles.

Code Implementation

from functools import lru_cache

class Solution:
    def canMouseWin(self, grid, catJump, mouseJump):
        ROWS, COLS = len(grid), len(grid[0])
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 'M':
                    mouse_start = (r, c)
                if grid[r][c] == 'C':
                    cat_start = (r, c)
                if grid[r][c] == 'F':
                    food = (r, c)

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

        @lru_cache(None)
        def dfs(mx, my, cx, cy, turn):
            if turn >= MAX_TURNS:
                return False
            if (mx, my) == (cx, cy):
                return False
            if (cx, cy) == food:
                return False
            if (mx, my) == food:
                return True

            if turn % 2 == 0:  # Mouse's turn
                for dx, dy in directions + [(0,0)]:
                    for dist in range(1 if (dx,dy)==(0,0) else mouseJump+1):
                        nx, ny = mx + dx*dist, my + dy*dist
                        if 0 <= nx < ROWS and 0 <= ny < COLS and grid[nx][ny] != '#':
                            if dfs(nx, ny, cx, cy, turn+1):
                                return True
                        else:
                            break
                return False
            else:  # Cat's turn
                for dx, dy in directions + [(0,0)]:
                    for dist in range(1 if (dx,dy)==(0,0) else catJump+1):
                        nx, ny = cx + dx*dist, cy + dy*dist
                        if 0 <= nx < ROWS and 0 <= ny < COLS and grid[nx][ny] != '#':
                            if not dfs(mx, my, nx, ny, turn+1):
                                return False
                        else:
                            break
                return True

        return dfs(mouse_start[0], mouse_start[1], cat_start[0], cat_start[1], 0)

class Solution {
public:
    int ROWS, COLS, MAX_TURNS = 1000;
    vector<string> grid;
    pair<int,int> food;
    int catJump, mouseJump;
    int memo[8][8][8][8][2][1050]; // [mx][my][cx][cy][turn%2][turn]

    bool dfs(int mx, int my, int cx, int cy, int turn, int isMouseTurn) {
        if (turn >= MAX_TURNS)
            return false;
        if (mx == cx && my == cy)
            return false;
        if (cx == food.first && cy == food.second)
            return false;
        if (mx == food.first && my == food.second)
            return true;

        int &res = memo[mx][my][cx][cy][isMouseTurn][turn];
        if (res != -1) return res;

        vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1},{0,0}};
        if (isMouseTurn) {
            for (auto d : dirs) {
                for (int jump = 0; jump <= (d==make_pair(0,0)?0:mouseJump); ++jump) {
                    int nx = mx + d.first*jump, ny = my + d.second*jump;
                    if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS || grid[nx][ny] == '#') break;
                    if (dfs(nx, ny, cx, cy, turn+1, 0)) return res = true;
                }
            }
            return res = false;
        } else {
            for (auto d : dirs) {
                for (int jump = 0; jump <= (d==make_pair(0,0)?0:catJump); ++jump) {
                    int nx = cx + d.first*jump, ny = cy + d.second*jump;
                    if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS || grid[nx][ny] == '#') break;
                    if (!dfs(mx, my, nx, ny, turn+1, 1)) return res = false;
                }
            }
            return res = true;
        }
    }

    bool canMouseWin(vector<string>& _grid, int _catJump, int _mouseJump) {
        grid = _grid;
        ROWS = grid.size();
        COLS = grid[0].size();
        catJump = _catJump;
        mouseJump = _mouseJump;
        memset(memo, -1, sizeof(memo));
        pair<int,int> mouse, cat;
        for (int i = 0; i < ROWS; ++i) {
            for (int j = 0; j < COLS; ++j) {
                if (grid[i][j] == 'M') mouse = {i,j};
                if (grid[i][j] == 'C') cat = {i,j};
                if (grid[i][j] == 'F') food = {i,j};
            }
        }
        return dfs(mouse.first, mouse.second, cat.first, cat.second, 0, 1);
    }
};

class Solution {
    final int MAX_TURNS = 1000;
    int ROWS, COLS, catJump, mouseJump;
    int[][][][][] memo;
    int[] food;
    String[] grid;

    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        this.grid = grid;
        this.ROWS = grid.length;
        this.COLS = grid[0].length();
        this.catJump = catJump;
        this.mouseJump = mouseJump;
        this.memo = new int[ROWS][COLS][ROWS][COLS][MAX_TURNS];
        int[] mouse = new int[2], cat = new int[2], food = new int[2];
        for (int i = 0; i < ROWS; ++i)
            for (int j = 0; j < COLS; ++j) {
                if (grid[i].charAt(j) == 'M') {
                    mouse[0] = i; mouse[1] = j;
                }
                if (grid[i].charAt(j) == 'C') {
                    cat[0] = i; cat[1] = j;
                }
                if (grid[i].charAt(j) == 'F') {
                    food[0] = i; food[1] = j;
                }
            }
        this.food = food;
        return dfs(mouse[0], mouse[1], cat[0], cat[1], 0, true);
    }

    private boolean dfs(int mx, int my, int cx, int cy, int turn, boolean mouseTurn) {
        if (turn >= MAX_TURNS) return false;
        if (mx == cx && my == cy) return false;
        if (cx == food[0] && cy == food[1]) return false;
        if (mx == food[0] && my == food[1]) return true;
        int val = memo[mx][my][cx][cy][turn];
        if (val != 0) return val == 1;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{0,0}};
        if (mouseTurn) {
            for (int[] d : dirs) {
                for (int jump = 0; jump <= (d[0]==0 && d[1]==0 ? 0 : mouseJump); ++jump) {
                    int nx = mx + d[0]*jump, ny = my + d[1]*jump;
                    if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS || grid[nx].charAt(ny) == '#') break;
                    if (dfs(nx, ny, cx, cy, turn+1, false)) {
                        memo[mx][my][cx][cy][turn] = 1;
                        return true;
                    }
                }
            }
            memo[mx][my][cx][cy][turn] = -1;
            return false;
        } else {
            for (int[] d : dirs) {
                for (int jump = 0; jump <= (d[0]==0 && d[1]==0 ? 0 : catJump); ++jump) {
                    int nx = cx + d[0]*jump, ny = cy + d[1]*jump;
                    if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS || grid[nx].charAt(ny) == '#') break;
                    if (!dfs(mx, my, nx, ny, turn+1, true)) {
                        memo[mx][my][cx][cy][turn] = -1;
                        return false;
                    }
                }
            }
            memo[mx][my][cx][cy][turn] = 1;
            return true;
        }
    }
}

var canMouseWin = function(grid, catJump, mouseJump) {
    const ROWS = grid.length, COLS = grid[0].length;
    let mouse, cat, food;
    for (let i = 0; i < ROWS; ++i) {
        for (let j = 0; j < COLS; ++j) {
            if (grid[i][j] === 'M') mouse = [i, j];
            if (grid[i][j] === 'C') cat = [i, j];
            if (grid[i][j] === 'F') food = [i, j];
        }
    }
    const MAX_TURNS = 1000;
    const memo = new Map();
    const dirs = [[-1,0],[1,0],[0,-1],[0,1],[0,0]];
    function stateKey(mx, my, cx, cy, turn) {
        return `${mx},${my},${cx},${cy},${turn}`;
    }
    function dfs(mx, my, cx, cy, turn) {
        if (turn >= MAX_TURNS) return false;
        if (mx === cx && my === cy) return false;
        if (cx === food[0] && cy === food[1]) return false;
        if (mx === food[0] && my === food[1]) return true;
        let key = stateKey(mx, my, cx, cy, turn);
        if (memo.has(key)) return memo.get(key);
        if (turn % 2 === 0) { // Mouse's turn
            for (let [dx, dy] of dirs) {
                for (let d = 0; d <= ((dx===0 && dy===0) ? 0 : mouseJump); ++d) {
                    let nx = mx + dx*d, ny = my + dy*d;
                    if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS || grid[nx][ny] === '#') break;
                    if (dfs(nx, ny, cx, cy, turn+1)) {
                        memo.set(key, true);
                        return true;
                    }
                }
            }
            memo.set(key, false);
            return false;
        } else { // Cat's turn
            for (let [dx, dy] of dirs) {
                for (let d = 0; d <= ((dx===0 && dy===0) ? 0 : catJump); ++d) {
                    let nx = cx + dx*d, ny = cy + dy*d;
                    if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS || grid[nx][ny] === '#') break;
                    if (!dfs(mx, my, nx, ny, turn+1)) {
                        memo.set(key, false);
                        return false;
                    }
                }
            }
            memo.set(key, true);
            return true;
        }
    }
    return dfs(mouse[0], mouse[1], cat[0], cat[1], 0);
};

AlgoMap.io

Want Help Cracking FAANG?