Cat and Mouse II - Practice Coding Problems

Cat and Mouse II - Problem

Array Math Dynamic Programming Graph Topological Sort Memoization Matrix Game Theory Hard

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

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

Mouse and Cat play according to the following rules:

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

The game can end in 4 ways:

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

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

Input & Output

Example 1 — Basic Grid

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

› Output: true

💡 Note: Mouse can reach food in 2 moves while cat needs more moves due to wall blocking and lower jump capacity

Example 2 — Cat Advantage

$ Input: grid = [["M",".",".",".","C"],[".",".",".",".","."],[".",".","F",".","."]], catJump = 3, mouseJump = 1

› Output: false

💡 Note: Cat has higher jump capacity and can intercept mouse before it reaches food

Example 3 — Wall Protection

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

› Output: true

💡 Note: Wall separates cat from mouse, giving mouse safe path to food with higher jump

Constraints

rows == grid.length
cols = grid[i].length
1 ≤ rows, cols ≤ 8
grid[i][j] consist only of characters 'C', 'M', 'F', '.', '#'
There is only one of each character 'C', 'M', and 'F' in grid
1 ≤ catJump, mouseJump ≤ 8

Visualization

Tap to expand

Understanding the Visualization

Game Setup

Grid with cat (C), mouse (M), food (F), walls (#)

Turn-Based Movement

Players alternate moves with jump limits

Win Conditions

Mouse wins if it reaches food first, cat wins otherwise

Key Takeaway

🎯 Key Insight: Use game theory - each position has deterministic outcome with optimal play

Asked in

G Google 12 M Microsoft 8 A Amazon 6

This is a classic minimax game theory problem. The key insight is modeling it as alternating turns where mouse tries to maximize winning probability while cat tries to minimize it. Best approach uses memoization to cache game states. Time: O(rows×cols×rows×cols×turns), Space: O(rows×cols×rows×cols×turns)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Game Simulation	O(4^(catJump+mouseJump))	O(rows × cols × turns)	Simulate all possible game sequences using recursive exploration
Memoization (Dynamic Programming)	O(rows × cols × rows × cols × turns)	O(rows × cols × rows × cols × turns)	Cache game state results to avoid redundant calculations

Brute Force Game Simulation — Algorithm Steps

Find initial positions of cat, mouse, and food
Recursively try all possible moves for current player
Check for terminal conditions (win/lose/draw)
Return true if mouse has a winning strategy

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Find cat, mouse, and food positions

Try All Moves

Recursively try every possible move for current player

Check Terminal

Determine if game ends (win/lose/timeout)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

typedef struct {
    int r, c;
} Position;

bool dfs(char grid[][100], int rows, int cols, Position mouse, Position cat, 
         Position food, int turn, int moves, int mouseJump, int catJump) {
    if (moves > 1000) return false;
    if (mouse.r == cat.r && mouse.c == cat.c) return false;
    if (mouse.r == food.r && mouse.c == food.c) return true;
    if (cat.r == food.r && cat.c == food.c) return false;
    
    if (turn == 0) {
        // Mouse turn - try all possible moves
        Position pos = mouse;
        if (dfs(grid, rows, cols, pos, cat, food, 1, moves + 1, mouseJump, catJump)) return true;
        
        for (int d = 0; d < 4; d++) {
            for (int step = 1; step <= mouseJump; step++) {
                int nr = mouse.r + directions[d][0] * step;
                int nc = mouse.c + directions[d][1] * step;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != '#') {
                    Position nextMouse = {nr, nc};
                    if (dfs(grid, rows, cols, nextMouse, cat, food, 1, moves + 1, mouseJump, catJump)) {
                        return true;
                    }
                } else {
                    break;
                }
            }
        }
        return false;
    } else {
        // Cat turn - all moves must fail for mouse to win
        Position pos = cat;
        if (!dfs(grid, rows, cols, mouse, pos, food, 0, moves + 1, mouseJump, catJump)) return false;
        
        for (int d = 0; d < 4; d++) {
            for (int step = 1; step <= catJump; step++) {
                int nr = cat.r + directions[d][0] * step;
                int nc = cat.c + directions[d][1] * step;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != '#') {
                    Position nextCat = {nr, nc};
                    if (!dfs(grid, rows, cols, mouse, nextCat, food, 0, moves + 1, mouseJump, catJump)) {
                        return false;
                    }
                } else {
                    break;
                }
            }
        }
        return true;
    }
}

bool solution(char grid[][100], int rows, int cols, int catJump, int mouseJump) {
    Position mousePos, catPos, foodPos;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 'M') {
                mousePos.r = i; mousePos.c = j;
            } else if (grid[i][j] == 'C') {
                catPos.r = i; catPos.c = j;
            } else if (grid[i][j] == 'F') {
                foodPos.r = i; foodPos.c = j;
            }
        }
    }
    
    return dfs(grid, rows, cols, mousePos, catPos, foodPos, 0, 0, mouseJump, catJump);
}

int main() {
    char grid[100][100];
    int catJump, mouseJump;
    
    // Simplified input parsing
    scanf("%d %d", &catJump, &mouseJump);
    
    bool result = solution(grid, 3, 3, catJump, mouseJump);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(catJump+mouseJump))

Each player can make up to 4 directions × jump length moves, explored recursively

✓ Linear Growth

Space Complexity

O(rows × cols × turns)

Recursion stack depth limited by grid size and turn limit

⚡ Linearithmic Space

15.6K Views

Medium Frequency

~45 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Game Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler