#1728

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Cat and Mouse II

Cat and Mouse II requires determining if the mouse can reach food before being caught using graph and topological ordering logic.

array math dynamic programming graph topological sort

Problem Statement

In Cat and Mouse II, you are given a grid representing a game environment with walls, floors, a cat, a mouse, and food. The mouse and cat take turns moving, with both able to jump up to mouseJump and catJump cells respectively, in four directions, but cannot move through walls. The mouse wins by reaching the food first, and the cat wins by catching the mouse before that.

Your task is to determine whether the mouse can guarantee a win, given the grid configuration and jump limits. Each move changes the state of the game, and the solution requires considering all reachable positions, capturing cycles, and applying game theory logic to propagate winning and losing states across the graph efficiently.

Examples

Example 1

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

Output: true

Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2

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

Output: true

Example details omitted.

Example 3

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

Output: false

Example details omitted.

Constraints

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

Solution Approach

Model game states as a graph

Represent each possible configuration of mouse and cat positions as a node in a graph. Track whose turn it is and which moves are allowed based on jump limits. Compute indegree for each node to prepare for backward propagation.

Apply topological ordering and DP

Use a queue to process all trivial terminal states first (mouse at food or cat catches mouse). Propagate winning and losing states backward using indegrees, updating parent nodes when all child states are determined.

Memoization to prune repeated states

Store results of visited states to avoid recomputation. Since the grid and jump constraints are small, memoization combined with topological ordering ensures all states are evaluated efficiently and prevents cycles from causing infinite loops.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the number of possible states, which is rows * cols for both cat and mouse times 2 for turn tracking. Using memoization and topological ordering reduces repeated computation and avoids exploring all permutations explicitly.

What Interviewers Usually Probe

Expecting graph modeling for positions and moves
Looking for topological sort with indegree to propagate outcomes
Checking for awareness of cycles and terminal state propagation

Common Pitfalls or Variants

Common pitfalls

Ignoring the turn when modeling states leads to incorrect results
Failing to account for jump limits can create invalid moves
Not using memoization may cause TLE due to state explosion

Follow-up variants

Change jump distances for cat and mouse and analyze win guarantees
Use rectangular grids larger than 8x8 to test DP scalability
Introduce multiple cats or mice to evaluate generalized topological propagation

FAQ

What is the main strategy for Cat and Mouse II?

Model each mouse and cat position as a node, compute indegrees, and apply topological ordering to determine winning states.

How does topological sorting help in this problem?

It propagates outcomes from known terminal states backward to other states, ensuring each state's result is computed only once.

Why memoization is crucial for Cat and Mouse II?

Memoization prevents recalculating repeated states, avoiding time limits exceeded due to combinatorial explosion of positions.

Can this approach handle larger grids or multiple jumps?

Yes, the graph and DP approach scales with jump constraints, but grid size beyond 8x8 may increase computation significantly.

Which pattern does this problem primarily demonstrate?

Graph indegree plus topological ordering pattern, combining game theory with DP to systematically resolve winning and losing states.

terminal

Solution

Solution 1: Topological Sorting

According to the problem description, the state of the game is determined by the mouse's position, the cat's position, and whose turn it is. The following states can be determined directly:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        m, n = len(grid), len(grid[0])
        cat_start = mouse_start = food = 0
        dirs = (-1, 0, 1, 0, -1)
        g_mouse = [[] for _ in range(m * n)]
        g_cat = [[] for _ in range(m * n)]

        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == "#":
                    continue
                v = i * n + j
                if c == "C":
                    cat_start = v
                elif c == "M":
                    mouse_start = v
                elif c == "F":
                    food = v
                for a, b in pairwise(dirs):
                    for k in range(mouseJump + 1):
                        x, y = i + k * a, j + k * b
                        if not (0 <= x < m and 0 <= y < n and grid[x][y] != "#"):
                            break
                        g_mouse[v].append(x * n + y)
                    for k in range(catJump + 1):
                        x, y = i + k * a, j + k * b
                        if not (0 <= x < m and 0 <= y < n and grid[x][y] != "#"):
                            break
                        g_cat[v].append(x * n + y)
        return self.calc(g_mouse, g_cat, mouse_start, cat_start, food) == 1

    def calc(
        self,
        g_mouse: List[List[int]],
        g_cat: List[List[int]],
        mouse_start: int,
        cat_start: int,
        hole: int,
    ) -> int:
        def get_prev_states(state):
            m, c, t = state
            pt = t ^ 1
            pre = []
            if pt == 1:
                for pc in g_cat[c]:
                    if ans[m][pc][1] == 0:
                        pre.append((m, pc, pt))
            else:
                for pm in g_mouse[m]:
                    if ans[pm][c][0] == 0:
                        pre.append((pm, c, 0))
            return pre

        n = len(g_mouse)
        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                degree[i][j][0] = len(g_mouse[i])
                degree[i][j][1] = len(g_cat[j])

        ans = [[[0, 0] for _ in range(n)] for _ in range(n)]
        q = deque()
        for i in range(n):
            ans[hole][i][1] = 1
            ans[i][hole][0] = 2
            ans[i][i][1] = ans[i][i][0] = 2
            q.append((hole, i, 1))
            q.append((i, hole, 0))
            q.append((i, i, 0))
            q.append((i, i, 1))
        while q:
            state = q.popleft()
            t = ans[state[0]][state[1]][state[2]]
            for prev_state in get_prev_states(state):
                pm, pc, pt = prev_state
                if pt == t - 1:
                    ans[pm][pc][pt] = t
                    q.append(prev_state)
                else:
                    degree[pm][pc][pt] -= 1
                    if degree[pm][pc][pt] == 0:
                        ans[pm][pc][pt] = t
                        q.append(prev_state)
        return ans[mouse_start][cat_start][0]

Continue Practicing

#2328 number of increasing paths in a grid #913 cat and mouse #329 longest increasing path in a matrix