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:
- If the cat occupies the same position as the mouse, the cat wins.
- If the cat reaches the food first, the cat wins.
- If the mouse reaches the food first, the mouse wins.
- 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:
- 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).
- If the mouse reaches the food, return true (mouse wins).
- If the cat reaches the food, return false (mouse loses).
- 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}
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.