这个题解使用了多源最短路径算法的思路，将问题建模成一个图，节点表示猫和老鼠的位置，状态为当前轮到谁移动。题解首先初始化每个位置的状态，如猫和老鼠处于同一位置或者猫和食物处于同一位置。然后，通过拓扑排序和状态传播，计算出从初始位置出发，在给定步数限制内老鼠是否能赢。主要逻辑是基于反向传播：从已知的输赢状态（如猫和老鼠同格，或者到达食物），向可能到达这些状态的前序位置传播输赢结果，直至包含初始位置的状态得到解决。
时间复杂度: O((rows * cols) ^ 2)
空间复杂度: O((rows * cols) ^ 2)
class Solution:
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
rows, cols = len(grid), len(grid[0])
# 计算位置序号的函数
def getPos(row: int, col: int) -> int:
return row * cols + col
# 初始化起始位置
startMouse = startCat = food = 0
for i, row in enumerate(grid):
for j, ch in enumerate(row):
if ch == 'M':
startMouse = getPos(i, j)
elif ch == 'C':
startCat = getPos(i, j)
elif ch == 'F':
food = getPos(i, j)
# 初始化状态的度数，考虑移动限制
total = rows * cols
degrees = [[[0, 0] for _ in range(total)] for _ in range(total)]
for mouse in range(total):
mouseRow, mouseCol = divmod(mouse, cols)
if grid[mouseRow][mouseCol] == '#':
continue
for cat in range(total):
catRow, catCol = divmod(cat, cols)
if grid[catRow][catCol] == '#':
continue
degrees[mouse][cat][MOUSE_TURN] += 1
degrees[mouse][cat][CAT_TURN] += 1
for dx, dy in DIRS:
# 老鼠的移动
row, col, jump = mouseRow + dx, mouseCol + dy, 1
while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= mouseJump:
nextMouse = getPos(row, col)
nextCat = getPos(catRow, catCol)
degrees[nextMouse][nextCat][MOUSE_TURN] += 1
row += dx
col += dy
jump += 1
# 猫的移动
row, col, jump = catRow + dx, catCol + dy, 1
while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= catJump:
nextMouse = getPos(mouseRow, mouseCol)
nextCat = getPos(row, col)
degrees[nextMouse][nextCat][CAT_TURN] += 1
row += dx
col += dy
jump += 1
# 初始化结果状态和队列
results = [[[[0, 0], [0, 0]] for _ in range(total)] for _ in range(total)]
q = deque()
# 处理特殊情况：猫和老鼠同格、猫和食物同格
for pos in range(total):
row, col = divmod(pos, cols)
if grid[row][col] == '#':
continue
results[pos][pos][MOUSE_TURN][0] = CAT_WIN
results[pos][pos][MOUSE_TURN][1] = 0
results[pos][pos][CAT_TURN][0] = CAT_WIN
results[pos][pos][CAT_TURN][1] = 0
q.append((pos, pos, MOUSE_TURN))
q.append((pos, pos, CAT_TURN))
# 处理老鼠和食物同格、猫和食物不同格的情况
for cat in range(total):
catRow, catCol = divmod(cat, cols)
if grid[catRow][catCol] == '#' or cat == food:
continue
results[food][cat][MOUSE_TURN][0] = MOUSE_WIN
results[food][cat][MOUSE_TURN][1] = 0
results[food][cat][CAT_TURN][0] = MOUSE_WIN
results[food][cat][CAT_TURN][1] = 0
q.append((food, cat, MOUSE_TURN))
q.append((food, cat, CAT_TURN))
# 使用拓扑排序处理所有状态，进行状态更新
while q:
mouse, cat, turn = q.popleft()
result = results[mouse][cat][turn][0]
moves = results[mouse][cat][turn][1]
for prevMouse, prevCat, prevTurn in getPrevStates(mouse, cat, turn):
if results[prevMouse][prevCat][prevTurn][0] == UNKNOWN:
if result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN:
results[prevMouse][prevCat][prevTurn][0] = result
results[prevMouse][prevCat][prevTurn][1] = moves + 1
q.append((prevMouse, prevCat, prevTurn))
else:
degrees[prevMouse][prevCat][prevTurn] -= 1
if degrees[prevMouse][prevCat][prevTurn] == 0:
loseResult = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN
results[prevMouse][prevCat][prevTurn][0] = loseResult
results[prevMouse][prevCat][prevTurn][1] = moves + 1
q.append((prevMouse, prevCat, prevTurn))
return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN and results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES
