README.md

1728. 猫和老鼠 II

English Version

题目描述

一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。

它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。

• 玩家由字符 'C' （代表猫）和 'M' （代表老鼠）表示。
• 地板由字符 '.' 表示，玩家可以通过这个格子。
• 墙用字符 '#' 表示，玩家不能通过这个格子。
• 食物用字符 'F' 表示，玩家可以通过这个格子。
• 字符 'C' ， 'M' 和 'F' 在 grid 中都只会出现一次。

猫和老鼠按照如下规则移动：

• 老鼠 先移动 ，然后两名玩家轮流移动。
• 每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出 grid 。
• catJump 和 mouseJump 是猫和老鼠分别跳一次能到达的最远距离，它们也可以跳小于最大距离的长度。
• 它们可以停留在原地。
• 老鼠可以跳跃过猫的位置。

游戏有 4 种方式会结束：

• 如果猫跟老鼠处在相同的位置，那么猫获胜。
• 如果猫先到达食物，那么猫获胜。
• 如果老鼠先到达食物，那么老鼠获胜。
• 如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。

给你 rows x cols 的矩阵 grid 和两个整数 catJump 和 mouseJump ，双方都采取最优策略，如果老鼠获胜，那么请你返回 true ，否则返回 false 。

 

示例 1：

输入：grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
输出：true
解释：猫无法抓到老鼠，也没法比老鼠先到达食物。

示例 2：

输入：grid = ["M.C...F"], catJump = 1, mouseJump = 4
输出：true

示例 3：

输入：grid = ["M.C...F"], catJump = 1, mouseJump = 3
输出：false

示例 4：

输入：grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
输出：false

示例 5：

输入：grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
输出：true

 

提示：

• rows == grid.length
• cols = grid[i].length
• 1 <= rows, cols <= 8
• grid[i][j] 只包含字符 'C' ，'M' ，'F' ，'.' 和 '#' 。
• grid 中只包含一个 'C' ，'M' 和 'F' 。
• 1 <= catJump, mouseJump <= 8

解法

方法一

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        dirs = [0, 1, 0, -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)

        # dp(i, j, k) := True if mouse can win w//
        # Cat on (i // 8, i % 8), mouse on (j // 8, j % 8), and turns = k
        @functools.lru_cache(None)
        def dp(cat: int, mouse: int, turn: int) -> bool:
            # We already search whole touchable grid
            if turn == nFloors * 2:
                return False

            if turn % 2 == 0:
                # mouse's turn
                i = mouse // n
                j = mouse % n
                for k in range(4):
                    for jump in range(mouseJump + 1):
                        x = i + dirs[k] * jump
                        y = j + dirs[k + 1] * jump
                        if x < 0 or x == m or y < 0 or y == n:
                            break
                        if grid[x][y] == "#":
                            break
                        if grid[x][y] == "F":  # Mouse eats the food, so mouse win
                            return True
                        if dp(cat, hash(x, y), turn + 1):
                            return True
                # Mouse can't win, so mouse lose
                return False
            else:
                # cat's turn
                i = cat // n
                j = cat % n
                for k in range(4):
                    for jump in range(catJump + 1):
                        x = i + dirs[k] * jump
                        y = j + dirs[k + 1] * jump
                        if x < 0 or x == m or y < 0 or y == n:
                            break
                        if grid[x][y] == "#":
                            break
                        if grid[x][y] == "F":  # Cat eats the food, so mouse lose
                            return False
                        nextCat = hash(x, y)
                        if nextCat == mouse:  # Cat catches mouse, so mouse lose
                            return False
                        if not dp(nextCat, mouse, turn + 1):
                            return False
                # Cat can't win, so mouse win
                return True

        return dp(cat, mouse, 0)