Leetcode 1728. Cat and Mouse II

Problem Explanation

In this problem, we have a cat and a mouse playing a game in a grid environment. The goal is to determine if the mouse can win the game if both players play optimally. The game can end in 4 different ways:

1. If the cat occupies the same position as the mouse, the cat wins.
2. If the cat reaches the food first, the cat wins.
3. If the mouse reaches the food first, the mouse wins.
4. If the mouse cannot reach the food within 1000 turns, the cat wins.

The environment is represented by a grid, where each position could be a wall (cannot be walked on), a floor (can be walked on), a player (cat or mouse), or food. The grid is constructed as such:

• 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.

We are given the grid, the cat's maximum jump length (catJump), and the mouse's maximum jump length (mouseJump). Our task is to return true if the mouse can win the game if both players play optimally, otherwise return false.

Solution Approach

The solution uses a dynamic programming approach with a three-dimensional memoization table, where dp[cat][mouse][turn] stores whether the mouse can win or lose given the current positions of the cat, mouse, and the number of turns taken.

We will recursively check all possible moves for both the cat and the mouse, each acting optimally based on their maximum jump distance (catJump and mouseJump).

The base cases for the recursion are:

1. If the turn count reaches the total number of accessible cells in the grid multiplied by 2 (since each player gets a turn), return false (mouse loses).
2. If the mouse reaches the food, return true (mouse wins).
3. If the cat reaches the food, return false (mouse loses).
4. If the cat catches the mouse, return false (mouse loses).

In each iteration for the mouse's or cat's turn, we will iterate through all possible moves based on their maximum jump distances and update the dynamic programming table accordingly.

Now let's walk through an example to understand the approach better.

Example

Given grid = ["####F","#C...","M...."], catJump = 1, and mouseJump = 2. The grid looks like:

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

We can see that initially, the cat is at position (1, 1) and the mouse is at position (2, 0). The food is at position (0, 4).

We will start with all possible moves for the mouse, taking into account that the mouse can jump up to 2 positions. After its turn, the possible moves will be:

• Move right 2 positions: ["####F","#C...","..M.."]
• Move right 1 position: ["####F","#C...",".M..."]
• Stay at the same position: ["####F","#C...","M...."]

Then, we will check all possible moves for the cat, taking into account that the cat can jump up to 1 position. After its turn, the possible moves will be:

• Move right 1 position: ["####F","##C..","M...."]
• Move down 1 position: ["####F","#....","MC..."]
• Stay at the same position: ["####F","#C...","M...."]

Now, we will proceed with recursing back and updating the dynamic programming table accordingly. In this scenario, the mouse can win, so the output will be true.

C++ Solution

1#include <vector>
2#include <string>
3
4using namespace std;
5
6class Solution {
7 public:
8  bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
9    m = grid.size();
10    n = grid[0].size();
11    int cat;    // cat's position
12    int mouse;  // mouse's position
13
14    for (int i = 0; i < m; ++i)
15      for (int j = 0; j < n; ++j) {
16        if (grid[i][j] != '#')
17          ++nFloors;
18        if (grid[i][j] == 'C')
19          cat = hash(i, j);
20        else if (grid[i][j] == 'M')
21          mouse = hash(i, j);
22      }
23
24    // dp[i][j][k] := true if mouse can win w/
25    // Cat on (i / 8, i % 8), mouse on (j / 8, j % 8), and turns = k
26    dp.resize(m * n, vector<vector<int>>(m * n, vector<int>(nFloors * 2, -1)));
27    return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump);
28  }
29
30 private:
31  const vector<int> dirs{0, 1, 0, -1, 0};
32  int m;
33  int n;
34  int nFloors = 0;
35  vector<vector<vector<int>>> dp;
36
37  bool canMouseWin(const vector<string>& grid, int cat, int mouse, int turn,
38                   const int& catJump, const int& mouseJump) {
39    // We already search whole touchable grid
40    if (turn == nFloors * 2)
41      return false;
42    if (dp[cat][mouse][turn] != -1)
43      return dp[cat][mouse][turn];
44
45    if (turn % 2 == 0) {
46      // mouse's turn
47      const int i = mouse / n;
48      const int j = mouse % n;
49      for (int k = 0; k < 4; ++k) {
50        for (int jump = 0; jump <= mouseJump; ++jump) {
51          const int x = i + dirs[k] * jump;
52          const int y = j + dirs[k + 1] * jump;
53          if (x < 0 || x == m || y < 0 || y == n)
54            break;
55          if (grid[x][y] == '#')
56            break;
57          if (grid[x][y] == 'F')  // Mouse eats the food, so mouse win
58            return dp[cat][mouse][turn] = true;
59          if (canMouseWin(grid, cat, hash(x, y), turn + 1, catJump, mouseJump))
60            return dp[cat][mouse][turn] = true;
61        }
62      }
63      // Mouse can't win, so mouse lose
64      return dp[cat][mouse][turn] = false;
65    } else {
66      // cat's turn
67      const int i = cat / n;
68      const int j = cat % n;
69      for (int k = 0; k < 4; ++k) {
70        for (int jump = 0; jump <= catJump; ++jump) {
71          const int x = i + dirs[k] * jump;
72          const int y = j + dirs[k + 1] * jump;
73          if (x < 0 || x == m || y < 0 || y == n)
74            break;
75          if (grid[x][y] == '#')
76            break;
77          if (grid[x][y] == 'F')  // Cat eats the food, so mouse lose
78            return dp[cat][mouse][turn] = false;
79          const int nextCat = hash(x, y);
80          if (nextCat == mouse)  // Cat catches mouse, so mouse lose
81            return dp[cat][mouse][turn] = false;
82          if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump))
83            return dp[cat][mouse][turn] = false;
84        }
85      }
86      // Cat can't win, so mouse win
87      return dp[cat][mouse][turn] = true;
88    }
89  }
90
91  int hash(int i, int j) {
92    return i * n + j;
93  }
94};
95```## Python Solution
96
97```python
98from typing import List
99
100class Solution:
101    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
102        m, n = len(grid), len(grid[0])
103        n_floors = sum(row.count('.') for row in grid) + 3
104        cat = mouse = food = 0
105
106        for i in range(m):
107            for j in range(n):
108                if grid[i][j] == 'C':
109                    cat = i, j
110                elif grid[i][j] == 'M':
111                    mouse = i, j
112                elif grid[i][j] == 'F':
113                    food = i, j
114
115        def can_win(cat: tuple, mouse: tuple, turn: int) -> bool:
116            if turn > 2 * n_floors: return False
117            if cat == food or cat == mouse: return False
118            if mouse == food: return True
119            if turn % 2:  # cat's turn
120                return not any(
121                    can_win((cx, cy), mouse, turn + 1)
122                    for cx, cy in valid_moves(cat, catJump)
123                )
124            else:  # mouse's turn
125                return any(
126                    can_win(cat, (mx, my), turn + 1)
127                    for mx, my in valid_moves(mouse, mouseJump)
128                )
129
130        def valid_moves(pos, jump):
131            x, y = pos
132            for dx in range(jump + 1):
133                for dy in range(jump - dx + 1):
134                    if dx != 0 or dy != 0:
135                        nx, ny = x + dx, y + dy
136                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != '#':
137                            yield nx, ny
138
139        return can_win(cat, mouse, 0)

JavaScript Solution

1class Solution {
2  canMouseWin(grid, catJump, mouseJump) {
3    const m = grid.length;
4    const n = grid[0].length;
5
6    let cat;
7    let mouse;
8    let food;
9    let nFloors = 0;
10
11    for (let i = 0; i < m; ++i) {
12      for (let j = 0; j < n; ++j) {
13        if (grid[i][j] !== "#") ++nFloors;
14        if (grid[i][j] === "C") cat = [i, j];
15        else if (grid[i][j] === "M") mouse = [i, j];
16        else if (grid[i][j] === "F") food = [i, j];
17      }
18    }
19
20    const dirs = [0, 1, 0, -1, 0];
21
22    const memo = new Map();
23
24    const canWin = (cat, mouse, turn) => {
25      if (turn > 2 * nFloors) return false;
26      if (cat.toString() === food.toString() || cat.toString() === mouse.toString()) return false;
27      if (mouse.toString() === food.toString()) return true;
28
29      const key = cat + "," + mouse + "," + turn;
30
31      if (memo.has(key)) return memo.get(key);
32
33      const [i, j] = turn % 2 === 0 ? cat : mouse;
34      const maxJump = turn % 2 === 0 ? catJump : mouseJump;
35      let canWinFlag = turn % 2;
36      
37      for (let d = 0; d < 4; ++d) {
38        for (let jump = 1; jump <= maxJump; ++jump) {
39          const x = i + dirs[d] * jump;
40          const y = j + dirs[d + 1] * jump;
41
42          if (x < 0 || x === m || y < 0 || y === n || grid[x][y] === "#") break;
43
44          if (turn % 2) canWinFlag &= canWin([x, y], mouse, turn + 1);
45          else canWinFlag |= canWin(cat, [x, y], turn + 1);
46        }
47      }
48      
49      memo.set(key, !!canWinFlag);
50      return !!canWinFlag;
51    };
52
53    return canWin(cat, mouse, 0);
54  }
55}