LeetCode 题解工作台
猫和老鼠 II
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。 它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。 玩家由字符 'C' （代表猫）和 'M' （代表老鼠）表示。 地板由字符 '.' 表示，玩家可以通过这个格子。 墙…
8
题型
6
代码语言
3
相关题
当前训练重点
困难 · 动态·规划
答案摘要
根据题目描述，游戏中的状态由老鼠的位置、猫的位置和移动方决定。当状态为以下情况，可以直接确定胜负： - 当猫和老鼠的位置相同时，猫获胜，这是猫的必胜状态，老鼠的必败状态。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。
它们所处的环境设定是一个 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.lengthcols = grid[i].length1 <= rows, cols <= 8grid[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:
m, n = len(grid), len(grid[0])
cat_start = mouse_start = food = 0
dirs = (-1, 0, 1, 0, -1)
g_mouse = [[] for _ in range(m * n)]
g_cat = [[] for _ in range(m * n)]
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == "#":
continue
v = i * n + j
if c == "C":
cat_start = v
elif c == "M":
mouse_start = v
elif c == "F":
food = v
for a, b in pairwise(dirs):
for k in range(mouseJump + 1):
x, y = i + k * a, j + k * b
if not (0 <= x < m and 0 <= y < n and grid[x][y] != "#"):
break
g_mouse[v].append(x * n + y)
for k in range(catJump + 1):
x, y = i + k * a, j + k * b
if not (0 <= x < m and 0 <= y < n and grid[x][y] != "#"):
break
g_cat[v].append(x * n + y)
return self.calc(g_mouse, g_cat, mouse_start, cat_start, food) == 1
def calc(
self,
g_mouse: List[List[int]],
g_cat: List[List[int]],
mouse_start: int,
cat_start: int,
hole: int,
) -> int:
def get_prev_states(state):
m, c, t = state
pt = t ^ 1
pre = []
if pt == 1:
for pc in g_cat[c]:
if ans[m][pc][1] == 0:
pre.append((m, pc, pt))
else:
for pm in g_mouse[m]:
if ans[pm][c][0] == 0:
pre.append((pm, c, 0))
return pre
n = len(g_mouse)
degree = [[[0, 0] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
degree[i][j][0] = len(g_mouse[i])
degree[i][j][1] = len(g_cat[j])
ans = [[[0, 0] for _ in range(n)] for _ in range(n)]
q = deque()
for i in range(n):
ans[hole][i][1] = 1
ans[i][hole][0] = 2
ans[i][i][1] = ans[i][i][0] = 2
q.append((hole, i, 1))
q.append((i, hole, 0))
q.append((i, i, 0))
q.append((i, i, 1))
while q:
state = q.popleft()
t = ans[state[0]][state[1]][state[2]]
for prev_state in get_prev_states(state):
pm, pc, pt = prev_state
if pt == t - 1:
ans[pm][pc][pt] = t
q.append(prev_state)
else:
degree[pm][pc][pt] -= 1
if degree[pm][pc][pt] == 0:
ans[pm][pc][pt] = t
q.append(prev_state)
return ans[mouse_start][cat_start][0]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the number of possible states, which is rows * cols for both cat and mouse times 2 for turn tracking. Using memoization and topological ordering reduces repeated computation and avoids exploring all permutations explicitly. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting graph modeling for positions and moves
- question_mark
Looking for topological sort with indegree to propagate outcomes
- question_mark
Checking for awareness of cycles and terminal state propagation
常见陷阱
外企场景- error
Ignoring the turn when modeling states leads to incorrect results
- error
Failing to account for jump limits can create invalid moves
- error
Not using memoization may cause TLE due to state explosion
进阶变体
外企场景- arrow_right_alt
Change jump distances for cat and mouse and analyze win guarantees
- arrow_right_alt
Use rectangular grids larger than 8x8 to test DP scalability
- arrow_right_alt
Introduce multiple cats or mice to evaluate generalized topological propagation