猫和老鼠 II

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

它们所处的环境设定是一个 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

这个题解使用了多源最短路径算法的思路，将问题建模成一个图，节点表示猫和老鼠的位置，状态为当前轮到谁移动。题解首先初始化每个位置的状态，如猫和老鼠处于同一位置或者猫和食物处于同一位置。然后，通过拓扑排序和状态传播，计算出从初始位置出发，在给定步数限制内老鼠是否能赢。主要逻辑是基于反向传播：从已知的输赢状态（如猫和老鼠同格，或者到达食物），向可能到达这些状态的前序位置传播输赢结果，直至包含初始位置的状态得到解决。

O((rows * cols) ^ 2)

O((rows * cols) ^ 2)