教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕《算法通关手册》题库中的困难题 0913. 猫和老鼠 展开完整讲解猫鼠博弈这一经典零和博弈 图论综合题的题面建模、状态设计以及如何用逆向思维 拓扑排序在 $O(n^3)$ 时间内判定在双方均采用最优策略时的胜负结果。读完本文你将掌握一套可迁移的从终局状态反推初始状态的博弈求解框架并能在 LeetCode 上直接运行给出的 Python 实现同时理解它与仓库中 Kahn 拓扑排序、DFS 拓扑排序 的底层联系。一、题目总览猫和老鼠的无向图追逐游戏1.1 题目大意两位玩家分别扮演猫和老鼠在一张无向图上进行追逐游戏两人轮流行动图以邻接表形式给出graph[a]是由所有满足「$ab$ 是一条边」的节点 $b$ 组成的列表老鼠从节点1出发并先手行动猫从节点2出发后手行动节点0是老鼠的洞每个玩家每次行动必须沿一条边移动到相邻节点如老鼠在节点 1就必须移动到graph[1]中的某个节点特殊限制猫不能进入洞节点 0。游戏在以下三种情形之一出现时结束猫与老鼠出现在同一节点→ 猫获胜老鼠到达洞节点 0→ 老鼠获胜某一位置重复出现玩家的位置与移动顺序和上一次行动完全相同→ 平局。要求在双方都采取最优策略的前提下返回游戏结果——老鼠获胜返回1猫获胜返回2平局返回0。1.2 数据范围$3 \le graph.length \le 50$节点数 $n$ 至多 50$1 \le graph[i].length graph.length$每个节点至少有一条出边游戏总能进行$0 \le graph[i][j] graph.length$且 $graph[i][j] \ne i$无自环各节点的邻接列表互不相同。1.3 示例示例 1输入graph [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] 输出0猫和老鼠在这张图上各自有多个策略分支双方都可以通过最优走法回避对方的必胜陷阱最终进入重复局面判定为平局。示例 2输入graph [[1,3],[0],[3],[0,2]] 输出1此时老鼠可以凭借更优的走位率先抵达节点 0洞从而获得胜利。提示示例配图为官方题面示意图重点在于理解邻接表结构与洞 0 / 起点 1 / 起点 2的位置关系本仓库文档仅以文本方式复述读者可直接在力扣题面查看原图。二、解题思路博弈论 拓扑排序2.1 为什么不能直接模拟猫鼠双方轮流行动、目标相互对立属于典型的零和博弈。若直接按当前局面谁优进行贪心或暴力搜索会陷入两个困难状态空间大$mouse \in [0, n)$、$cat \in [0, n)$、行动方 $turn \in {1, 2}$共 $2n^2$ 个状态存在平局循环某些状态既不是任何一方的必胜态也不会通向终结局面而是会陷入重复循环。因此需要一种能够同时处理必胜 / 必败 / 平局三类结果的确定性算法——**逆向拓扑排序Retrograde Analysis**恰好满足需求。2.2 状态与结果定义定义三元组状态$(mouse, cat, turn)$老鼠在节点 $mouse$猫在节点 $cat$当前轮到 $turn$ 行动$1$ 表示老鼠$2$ 表示猫。状态结果取值$0$平局DRAW$1$老鼠获胜MOUSE_WIN$2$猫获胜CAT_WIN。2.3 逆向思维从终局反推初始状态与正向模拟不同拓扑排序解法从已知结果的终结状态出发反向推导前驱状态。其正确性依据是博弈论的经典递推规则若某一状态存在一个后继状态对当前行动方有利则当前状态对当前行动方有利当前玩家会主动选择这条最优路线若某一状态的所有后继状态都对对手有利即对当前行动方全部不利则当前状态对当前行动方不利。具体分三步初始化终结状态老鼠到达洞口$mouse 0$→ 老鼠获胜结果置为1猫抓到老鼠$mouse cat$且 $cat \ne 0$→ 猫获胜结果置为2。按逆拓扑序传播结果从已知结果的状态出队考察所有可能的前驱状态。前驱状态若存在通往己方获胜的后继直接判胜否则将其剩余未定后继数出度减一当出度归零时说明所有后继都对己方不利判负。返回初始状态结果$(1, 2, 1)$即老鼠在 1、猫在 2、老鼠先手时的最终胜负值。这一从终局反推的技巧在仓库 06_05_graph_topological_sorting.md 讲解的拓扑排序思想上一脉相承——只不过经典拓扑排序通过入度归零确定依赖顺序这里通过出度归零确定所有分支均不利的必败状态。三、完整代码实现3.1 Python 实现可直接提交class Solution: def catMouseGame(self, graph: List[List[int]]) - int: n len(graph) DRAW, MOUSE_WIN, CAT_WIN 0, 1, 2 # 状态(mouse, cat, turn)turn1 表示老鼠turn2 表示猫 # 结果0平局1老鼠赢2猫赢 result [[[DRAW] * 3 for _ in range(n)] for _ in range(n)] degree [[[0] * 3 for _ in range(n)] for _ in range(n)] # 计算每个状态的出度后继状态数 for mouse in range(n): for cat in range(n): degree[mouse][cat][1] len(graph[mouse]) # 猫不能移动到洞节点 0因此出度要去掉 0 degree[mouse][cat][2] len([node for node in graph[cat] if node ! 0]) # 初始化队列已知结果的状态 from collections import deque queue deque() for cat in range(n): for turn in [1, 2]: # 老鼠到达洞口老鼠赢 result[0][cat][turn] MOUSE_WIN queue.append((0, cat, turn)) # 猫抓到老鼠但猫不能在洞口猫赢 if cat 0: result[cat][cat][turn] CAT_WIN queue.append((cat, cat, turn)) # 拓扑排序逆向传播 while queue: mouse, cat, turn queue.popleft() current_result result[mouse][cat][turn] if turn 1: # 当前是老鼠的回合推导上一步猫的状态 for prev_cat in graph[cat]: if prev_cat 0: # 猫不能进洞 continue if result[mouse][prev_cat][2] ! DRAW: continue if current_result CAT_WIN: # 如果老鼠这步后猫赢说明猫的上一步可以导致猫赢 result[mouse][prev_cat][2] CAT_WIN queue.append((mouse, prev_cat, 2)) else: # 否则减少出度 degree[mouse][prev_cat][2] - 1 if degree[mouse][prev_cat][2] 0: # 所有后继状态都对猫不利猫输 result[mouse][prev_cat][2] MOUSE_WIN queue.append((mouse, prev_cat, 2)) else: # 当前是猫的回合推导上一步老鼠的状态 for prev_mouse in graph[mouse]: if result[prev_mouse][cat][1] ! DRAW: continue if current_result MOUSE_WIN: # 如果猫这步后老鼠赢说明老鼠的上一步可以导致老鼠赢 result[prev_mouse][cat][1] MOUSE_WIN queue.append((prev_mouse, cat, 1)) else: # 否则减少出度 degree[prev_mouse][cat][1] - 1 if degree[prev_mouse][cat][1] 0: # 所有后继状态都对老鼠不利老鼠输 result[prev_mouse][cat][1] CAT_WIN queue.append((prev_mouse, cat, 1)) return result[1][2][1]3.2 关键实现细节逐行解读出度计算第 1418 行$turn1$老鼠回合的出度是len(graph[mouse])$turn2$猫回合的出度必须过滤掉节点 0因为猫不能进洞这与题面约束严格对应。终结状态初始化第 2331 行对任意 $cat$ 与任意 $turn$$(0, cat, turn)$ 都是老鼠必胜$(cat, cat, turn)$$cat0$ 时都是猫必胜。它们作为拓扑排序的源点入队。回合反向传播第 3362 行当前结果对上一步行动方不利时如当前老鼠回合得到CAT_WIN说明猫的上一步 $(mouse, prev_cat, 2)$ 存在一个导致猫赢的后继直接给前驱状态判胜否则将前驱状态的degree减一代表这个前驱状态的一个后继分支已确定对己方不利当degree归零时说明其所有后继都对己方不利从而判定前驱状态必败。返回初始局面result[1][2][1]即老鼠在 1、猫在 2、老鼠先手的最终结果。3.3 复杂度分析时间复杂度$O(n^3)$其中 $n$ 是图中节点数$n \le 50$。每个状态至多入队一次每次出队需要遍历前驱边总边数为 $O(n^2)$ 量级状态总数为 $O(n^2)$综合为 $O(n^3)$。空间复杂度$O(n^2)$需要存储全部状态的result与degree数组各为 $n \times n \times 3$。在 $n50$ 的规模下$O(n^3)$ 完全可接受这也是该解法能在力扣通过全部测试用例的原因。四、与仓库源码的联动拓扑排序在 AlgoNote 中的完整脉络4.1 算法分类归属在《算法通关手册》的分类体系中本题被归入图、拓扑排序、记忆化搜索、数学、动态规划、博弈复合标签可见于 00_06_categories_list.md 的题解总表同时被收录进 00_05_solutions_list.md 的完整题解清单。4.2 底层的拓扑排序实现对照本解法本质上是在博弈状态图上做逆向拓扑排序其队列驱动的核心结构与仓库中 Graph-Topological-Sorting-Kahn.py 一脉相承Kahn 算法维护indegrees入度字典将入度为 0 的节点入队出队时将其所有后继节点的入度减一入度归零者继续入队直至队列为空若最终拓扑序列长度不等于节点总数则说明图中存在环。本题的逆向版本则维护degree剩余未定后继数将结果已定的终结状态入队出队时将其前驱状态的剩余后继数减一归零者判定为必败并入队。可以对照观察# 来自 codes/python/06_graph/Graph-Topological-Sorting-Kahn.py while S: u S.pop() # 从集合中选择一个没有前驱的顶点 order.append(u) # 将其输出到拓扑序列 order 中 for v in graph[u]: # 遍历顶点 u 的邻接顶点 v indegrees[v] - 1 # 删除从顶点 u 出发的有向边 if indegrees[v] 0: # 如果删除该边后顶点 v 的入度变为 0 S.append(v) # 将其放入集合 S 中同样的度归零 → 入队 → 扩散模式前者用于判断有向无环图中的依赖顺序后者用于在博弈状态图中扩散必胜 / 必败结论。仓库还提供 DFS 版本 Graph-Topological-Sorting-DFS.py可作为理解拓扑序两种实现方式的补充阅读材料。4.3 从题库到手册的延伸学习本题的逆向博弈思想与以下仓库资源相互印证适合按序进阶06_05_graph_topological_sorting.md拓扑排序完整理论Kahn 与 DFS 两种实现、环检测、典型应用07_04_backtracking_algorithm.md博弈类问题另一常用手段——带记忆化搜索的回溯配合turn轮换与结果缓存可处理较小规模的类似博弈题题库中的其他两人最优博弈类题目如 0292 Nim 游戏、0486 预测赢家等可分别从 nims 相关文档 与 predict-the-winner.md 入手对照练习。五、总结0913 猫和老鼠是一道把零和博弈与图论逆向拓扑排序结合到极致的困难题其核心方法论可以提炼为三步建模把局面压缩为 $(mouse, cat, turn)$ 三元组状态明确三类结果鼠胜 / 猫胜 / 平局逆向从老鼠到洞猫鼠同点两个确定终局反向传播用存在有利后继 → 胜全部不利 → 负的规则在状态图上扩散结论收敛未被任何结果覆盖的状态自然就是平局循环局面最终返回初始状态 $(1, 2, 1)$ 的结果即可。掌握这套终局反推 出度归零的框架后遇到任何双方最优博弈 平局处理的题目你都可以快速套用这也正是《算法通关手册》在 0913. 猫和老鼠 中沉淀下来的核心解题范式。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 207「课程表」用图论拓扑排序判断课程依赖环AlgoNote 算法通关手册实战解析LeetCode 207「课程表」用图论拓扑排序判断课程依赖环AlgoNote 算法通关手册实战解析 导读 本篇技术指南基于 AlgoNote「算法通关手教程文档知识库AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析 全排列Permutations是回溯算法最经典的入门问题也是算法面试教程文档知识库AlgoNote 算法通关手册LeetCode 0444 序列重建题解——用「唯一拓扑排序」判断最短超序列AlgoNote 算法通关手册LeetCode 0444 序列重建题解——用「唯一拓扑排序」判断最短超序列 本篇是「算法通关手册」AlgoNote 中 Lee教程文档知识库上一篇NSC_BUILDER30功能集成的Switch游戏文件处理全能工具下一篇QKeyMapper按键映射工具终极指南让游戏手柄玩转所有PC游戏创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考