1728. Cat and Mouse II
Hard
50 Points
Array
Math
Dynamic Programming
Graph
Topological Sort
Memoization
Matrix
Game Theory
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.
Mouse and Cat play according to the following rules:
The game can end in 4 ways:
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.
Examples
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.lengthcols = grid[i].length1 <= rows, cols <= 8grid[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
1728. Cat and Mouse II
Hard
50 Points
Array
Math
Dynamic Programming
Graph
Topological Sort
Memoization
Matrix
Game Theory
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.
Mouse and Cat play according to the following rules:
The game can end in 4 ways:
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.
Examples
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.lengthcols = grid[i].length1 <= rows, cols <= 8grid[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