题目
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
- 如果猫和老鼠出现在同一个节点，猫获胜。
- 如果老鼠到达洞中，老鼠获胜。
- 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
- 如果老鼠获胜，则返回 1；
- 如果猫获胜，则返回 2；
- 如果平局，则返回 0 。
示例 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
解题
方法一：DFS+记忆化递归
为什么当 turns ≥ 2 n \textit{turns} ≥2nturns≥2n 时，游戏结果是平局呢？
如果游戏已经进行了 2n 轮，但是仍然没有任何一方获胜，此时猫和老鼠各移动了 n 次，该移动次数等于图中的节点数，因此一定存在一个老鼠到达过至少两次的节点，以及一定存在一个猫到达过至少两次的节点。
对于老鼠而言，即使按照最优策略，也无法躲入洞内，而是只能回到一个已经到达过的节点。当老鼠回到一个在过去的某个回合已经到达过的节点时，猫可能回到在相同回合已经到达过的节点，也可能移动到一个更有利于猫获胜的节点，不可能移动到一个更有利于老鼠获胜的节点（否则猫就不是按照最优策略参与游戏）。如果猫回到在相同回合已经到达过的节点，则形成循环，因此是平局；如果猫移动到一个更有利于猫获胜的节点，则老鼠的获胜机会更小，因此老鼠无法获胜。
同理可知，如果猫按照最优策略也只能回到一个已经到达过的节点，则猫无法获胜。
因此当猫和老鼠分别回到一个已经到达过的节点时，猫和老鼠都无法获胜，游戏结果是平局。
class Solution { public: static const int DRAW=0;//平局 static const int MOUSE_WIN=1;//老鼠赢 static const int CAT_WIN=2;//猫赢 int catMouseGame(vector<vector<int>>& graph) { int n=graph.size(); vector<vector<vector<int>>> memo=vector<vector<vector<int>>>(n,vector<vector<int>>(n,vector<int>(2*n,-1))); return dfs(graph,n,memo,2,1,0); } int dfs(vector<vector<int>>& graph,int n,vector<vector<vector<int>>>& memo,int catPos,int mousePos,int turns){ // 超过节点数两倍，可以确定为平局 if(turns>=2*n) return 0; // 缓存中有，直接返回 if(memo[catPos][mousePos][turns]!=-1) return memo[catPos][mousePos][turns]; // 老鼠赢 if(mousePos==0) return memo[catPos][mousePos][turns]=MOUSE_WIN; // 猫赢 if(catPos==mousePos) return memo[catPos][mousePos][turns]=CAT_WIN; // turns 为偶数是轮到老鼠走，为奇数是轮到猫走 if(turns%2==0){ // 老鼠最坏情况是猫赢 int ans=CAT_WIN; // 尝试走到下一个节点 for(int nextPos:graph[mousePos]){ int nextAns=dfs(graph,n,memo,catPos,nextPos,turns+1); // 如果老鼠可以赢，直接返回 if(nextAns==MOUSE_WIN) return memo[catPos][mousePos][turns]=MOUSE_WIN; // 有平局，先记录为平局，后面如果有老鼠可以赢的场景，通过上述语句可以返回 if(nextAns==DRAW) ans=DRAW; } // 返回老鼠走的结果 return memo[catPos][mousePos][turns]=ans; } else{ // 猫最坏情况是老鼠赢 int ans=MOUSE_WIN; for(int nextPos:graph[catPos]){ // 注意猫不能走到0号节点 if (nextPos != 0) { // 尝试进入下一个节点 int nextAns=dfs(graph,n,memo,nextPos,mousePos,turns+1); // 如果猫可以赢，直接返回 if(nextAns==CAT_WIN) return memo[catPos][mousePos][turns]=CAT_WIN; // 有平局，先记录为平局，后面如果有猫可以赢的场景，通过上述语句可以返回 if(nextAns==DRAW) ans=DRAW; } } // 返回猫走的结果 return memo[catPos][mousePos][turns]=ans; } } };
