#1728

Cat and Mouse II

master · 1705 · lc hard +32 · verified · 40.4% accepted · 287 likes · top 20%

Description

A cat and mouse play a game on a rows x cols grid. Cells are walls ('#'), open ('.'), food ('F'), cat start ('C'), or mouse start ('M'). Mouse moves first; both jump up to their max distances (mouseJump, catJump) in four directions without crossing walls. Cat wins if it occupies the mouse's position, reaches food first, or the mouse can't reach food within 1000 turns. Mouse wins by reaching food first.

Return true if Mouse can win with optimal play from both sides.

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

Code

1

2

3

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool: