1728. Cat and Mouse II LeetCode Solution
In this guide, you will get 1728. Cat and Mouse II LeetCode Solution with the best time and space complexity. The solution to Cat and Mouse II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Cat and Mouse II solution in C++
- Cat and Mouse II solution in Java
- Cat and Mouse II solution in Python
- Additional Resources
Problem Statement of Cat and Mouse II
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.
Example 1:
Input: grid = [“####F”,”#C…”,”M….”], catJump = 1, mouseJump = 2
Output: true
Explanation: 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 3:
Input: grid = [“M.C…F”], catJump = 1, mouseJump = 3
Output: false
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
Complexity Analysis
- Time Complexity: O(m^3n^3 \cdot (m + n))
- Space Complexity: O(m^3n^3)
1728. Cat and Mouse II LeetCode Solution in C++
class Solution {
public:
bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
const int m = grid.size();
const int n = grid[0].size();
int nFloors = 0;
int cat; // cat's position
int mouse; // mouse's position
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '#')
++nFloors;
if (grid[i][j] == 'C')
cat = hash(i, j, n);
else if (grid[i][j] == 'M')
mouse = hash(i, j, n);
}
vector<vector<vector<int>>> mem(
m * n, vector<vector<int>>(m * n, vector<int>(nFloors * 2, -1)));
return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump, m, n, nFloors,
mem);
}
private:
static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// Returns true if the mouse can win, where the cat is on (i / 8, i % 8), the
// mouse is on (j / 8, j % 8), and the turns is k.
bool canMouseWin(const vector<string>& grid, int cat, int mouse, int turn,
const int& catJump, const int& mouseJump, const int& m,
const int& n, const int& nFloors,
vector<vector<vector<int>>>& mem) {
// We already search the whole touchable grid.
if (turn == nFloors * 2)
return false;
if (mem[cat][mouse][turn] != -1)
return mem[cat][mouse][turn];
if (turn % 2 == 0) {
// the mouse's turn
const int i = mouse / n;
const int j = mouse % n;
for (const auto& [dx, dy] : dirs) {
for (int jump = 0; jump <= mouseJump; ++jump) {
const int x = i + dx * jump;
const int y = j + dy * jump;
if (x < 0 || x == m || y < 0 || y == n)
break;
if (grid[x][y] == '#')
break;
// The mouse eats the food, so the mouse wins.
if (grid[x][y] == 'F')
return mem[cat][mouse][turn] = true;
if (canMouseWin(grid, cat, hash(x, y, n), turn + 1, catJump,
mouseJump, m, n, nFloors, mem))
return mem[cat][mouse][turn] = true;
}
}
// The mouse can't win, so the mouse loses.
return mem[cat][mouse][turn] = false;
} else {
// the cat's turn
const int i = cat / n;
const int j = cat % n;
for (const auto& [dx, dy] : dirs) {
for (int jump = 0; jump <= catJump; ++jump) {
const int x = i + dx * jump;
const int y = j + dy * jump;
if (x < 0 || x == m || y < 0 || y == n)
break;
if (grid[x][y] == '#')
break;
// The cat eats the food, so the mouse loses.
if (grid[x][y] == 'F')
return mem[cat][mouse][turn] = false;
const int nextCat = hash(x, y, n);
// The cat catches the mouse, so the mouse loses.
if (nextCat == mouse)
return mem[cat][mouse][turn] = false;
if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump,
m, n, nFloors, mem))
return mem[cat][mouse][turn] = false;
}
}
// The cat can't win, so the mouse wins.
return mem[cat][mouse][turn] = true;
}
}
int hash(int i, int j, int n) {
return i * n + j;
}
};
/* code provided by PROGIEZ */1728. Cat and Mouse II LeetCode Solution in Java
class Solution {
public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
final int m = grid.length;
final int n = grid[0].length();
int nFloors = 0;
int cat = 0; // cat's position
int mouse = 0; // mouse's position
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (grid[i].charAt(j) != '#')
++nFloors;
if (grid[i].charAt(j) == 'C')
cat = hash(i, j, n);
else if (grid[i].charAt(j) == 'M')
mouse = hash(i, j, n);
}
Boolean[][][] mem = new Boolean[m * n][m * n][nFloors * 2];
return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump, m, n, nFloors, mem);
}
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// Returns true if the mouse can win, where the cat is on (i / 8, i % 8), the
// mouse is on (j / 8, j % 8), and the turns is k.
private boolean canMouseWin(String[] grid, int cat, int mouse, int turn, int catJump,
int mouseJump, int m, int n, int nFloors, Boolean[][][] mem) {
// We already search the whole touchable grid.
if (turn == nFloors * 2)
return false;
if (mem[cat][mouse][turn] != null)
return mem[cat][mouse][turn];
if (turn % 2 == 0) {
// the mouse's turn
int i = mouse / n;
int j = mouse % n;
for (int[] dir : dirs) {
for (int jump = 0; jump <= mouseJump; ++jump) {
int x = i + dir[0] * jump;
int y = j + dir[1] * jump;
if (x < 0 || x == m || y < 0 || y == n)
break;
if (grid[x].charAt(y) == '#')
break;
// The mouse eats the food, so the mouse wins.
if (grid[x].charAt(y) == 'F')
return mem[cat][mouse][turn] = true;
if (canMouseWin(grid, cat, hash(x, y, n), turn + 1, catJump, mouseJump, m, n, nFloors,
mem))
return mem[cat][mouse][turn] = true;
}
}
// The mouse can't win, so the mouse loses.
return mem[cat][mouse][turn] = false;
} else {
// the cat's turn
final int i = cat / n;
final int j = cat % n;
for (int[] dir : dirs)
for (int jump = 0; jump <= catJump; ++jump) {
final int x = i + dir[0] * jump;
final int y = j + dir[1] * jump;
if (x < 0 || x == m || y < 0 || y == n)
break;
if (grid[x].charAt(y) == '#')
break;
// The cat eats the food, so the mouse loses.
if (grid[x].charAt(y) == 'F')
return mem[cat][mouse][turn] = false;
final int nextCat = hash(x, y, n);
if (nextCat == mouse)
return mem[cat][mouse][turn] = false;
if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump, m, n, nFloors, mem))
return mem[cat][mouse][turn] = false;
}
// The cat can't win, so the mouse wins.
return mem[cat][mouse][turn] = true;
}
}
private int hash(int i, int j, int n) {
return i * n + j;
}
}
// code provided by PROGIEZ1728. Cat and Mouse II LeetCode Solution in Python
class Solution:
def canMouseWin(self, grid: list[str], catJump: int, mouseJump: int) -> bool:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(grid)
n = len(grid[0])
nFloors = 0
cat = 0 # cat's position
mouse = 0 # mouse's position
def hash(i: int, j: int) -> int:
return i * n + j
for i in range(m):
for j in range(n):
if grid[i][j] != '#':
nFloors += 1
if grid[i][j] == 'C':
cat = hash(i, j)
elif grid[i][j] == 'M':
mouse = hash(i, j)
@functools.lru_cache(None)
def dp(cat: int, mouse: int, turn: int) -> bool:
"""
Returns True if the mouse can win, where the cat is on (i / 8, i % 8), the
mouse is on (j / 8, j % 8), and the turns is k.
"""
# We already search the whole touchable grid.
if turn == nFloors * 2:
return False
if turn % 2 == 0:
# the mouse's turn
i = mouse // n
j = mouse % n
for dx, dy in dirs:
for jump in range(mouseJump + 1):
x = i + dx * jump
y = j + dy * jump
if x < 0 or x == m or y < 0 or y == n:
break
if grid[x][y] == '#':
break
# The mouse eats the food, so the mouse wins.
if grid[x][y] == 'F':
return True
if dp(cat, hash(x, y), turn + 1):
return True
# The mouse can't win, so the mouse loses.
return False
else:
# the cat's turn
i = cat // n
j = cat % n
for dx, dy in dirs:
for jump in range(catJump + 1):
x = i + dx * jump
y = j + dy * jump
if x < 0 or x == m or y < 0 or y == n:
break
if grid[x][y] == '#':
break
# The cat eats the food, so the mouse loses.
if grid[x][y] == 'F':
return False
nextCat = hash(x, y)
# The cat catches the mouse, so the mouse loses.
if nextCat == mouse:
return False
if not dp(nextCat, mouse, turn + 1):
return False
# The cat can't win, so the mouse wins.
return True
return dp(cat, mouse, 0)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.