前言

\n

博弈知识介绍

\n

这道题是博弈问题，猫和老鼠都按照最优策略参与游戏。

\n

在阐述具体解法之前，首先介绍博弈问题中的三个概念：必胜状态、必败状态与必和状态。

\n

\n
对于特定状态，如果游戏已经结束，则根据结束时的状态决定必胜状态、必败状态与必和状态。
\n
- \n
  如果分出胜负，则该特定状态对于获胜方为必胜状态，对于落败方为必败状态。
  \n
- \n
  如果是平局，则该特定状态对于双方都为必和状态。
  \n
\n
\n
从特定状态开始，如果存在一种操作将状态变成必败状态，则当前玩家可以选择该操作，将必败状态留给对方玩家，因此该特定状态对于当前玩家为必胜状态。
\n
\n
从特定状态开始，如果所有操作都会将状态变成必胜状态，则无论当前玩家选择哪种操作，都会将必胜状态留给对方玩家，因此该特定状态对于当前玩家为必败状态。
\n
\n
从特定状态开始，如果任何操作都不能将状态变成必败状态，但是存在一种操作将状态变成必和状态，则当前玩家可以选择该操作，将必和状态留给对方玩家，因此该特定状态对于双方玩家都为必和状态。
\n

\n

对于每个玩家，最优策略如下：

\n

\n
争取将必胜状态留给自己，将必败状态留给对方玩家。
\n
\n
在自己无法到达必胜状态的情况下，争取将必和状态留给自己。
\n

\n

自顶向下动态规划解法介绍

\n

博弈问题通常可以使用动态规划求解。这道题由于数据规模的原因，动态规划方法不适用，因此只是介绍。

\n

使用三维数组 $\\textit{dp}$ 表示状态，$\\textit{dp}[\\textit{mouse}][\\textit{cat}][\\textit{turns}]$ 表示从老鼠位于节点 $\\textit{mouse}$、猫位于节点 $\\textit{cat}$、游戏已经进行了 $\\textit{turns}$ 轮的状态开始，猫和老鼠都按照最优策略的情况下的游戏结果。假设图中的节点数是 $n$，则有 $0 \\le \\textit{mouse}, \\textit{cat} < n$。

\n

由于游戏的初始状态是老鼠位于节点 $1$，猫位于节点 $2$，因此 $\\textit{dp}[1][2][0]$ 为从初始状态开始的游戏结果。

\n

动态规划的边界条件为可以直接得到游戏结果的状态，包括以下三种状态：

\n

\n
如果 $\\textit{mouse} = 0$，老鼠躲入洞里，则老鼠获胜，因此对于任意 $\\textit{cat}$ 和 $\\textit{turns}$ 都有 $\\textit{dp}[0][\\textit{cat}][\\textit{turns}] = 1$，该状态为老鼠的必胜状态，猫的必败状态。
\n
\n
如果 $\\textit{cat} = \\textit{mouse}$，猫和老鼠占据相同的节点，则猫获胜，因此当 $\\textit{cat} = \\textit{mouse}$ 时，对于任意 $\\textit{mouse}$、$\\textit{cat}$ 和 $\\textit{turns}$ 都有 $\\textit{dp}[\\textit{mouse}][\\textit{cat}][\\textit{turns}] = 2$，该状态为老鼠的必败状态，猫的必胜状态。注意猫不能移动到节点 $0$，因此当 $\\textit{mouse} = 0$ 时，一定有 $\\textit{cat} \\ne \\textit{mouse}$。
\n
\n
如果 $\\textit{turns} \\ge 2n(n - 1)$，则是平局，该状态为双方的必和状态。
\n
\n
由于游戏中的每个局面由老鼠的位置、猫的位置和轮到移动的一方三个因素确定，老鼠可能的位置数是 $n$，因此猫可能的位置数是 $n - 1$（由于猫不能移动到节点 $0$），轮到移动的一方有 $2$ 种可能，因此游戏中所有可能的局面数是 $2n(n - 1)$。
\n
根据抽屉原理可知，当游戏进行了 $2n(n - 1)$ 轮时，一定存在至少一个猫和老鼠重复经过的局面。由于猫和老鼠都按照最优策略参与游戏，对于同一个局面，游戏结果是相同的。
\n
考虑该重复经过的局面。从该局面开始，双方按照最优策略移动，结果只能回到该局面，任何一方都无法让己方到达必胜状态，让对方到达必败状态，因此该状态对于双方都不是必胜状态，只能是必和状态。
\n
如果该重复经过的局面和初始局面相同，则初始局面即为双方的必和状态。如果该重复经过的局面和初始局面不同，则从初始局面开始，双方按照最优策略移动，结果只能到达双方的必和状态，任何一方都无法让己方到达必胜状态，让对方到达必败状态，因此初始局面对于双方都不是必胜状态，只能是必和状态。
\n
综上所述，如果游戏进行了 $2n(n - 1)$ 轮还没有任何一方获胜，则是平局。
\n
\n

\n

动态规划的状态转移需要考虑当前玩家所有可能的移动，选择最优策略的移动。

\n

由于老鼠先开始移动，猫后开始移动，因此可以根据游戏已经进行的轮数 $\\textit{turns}$ 的奇偶性决定当前轮到的玩家，当 $\\textit{turns}$ 是偶数时轮到老鼠移动，当 $\\textit{turns}$ 是奇数时轮到猫移动。

\n

如果轮到老鼠移动，则对于老鼠从当前节点移动一次之后可能到达的每个节点，进行如下操作：

\n

\n
如果存在一个节点，老鼠到达该节点之后，老鼠可以获胜，则老鼠到达该节点之后的状态为老鼠的必胜状态，猫的必败状态，因此在老鼠移动之前的当前状态为老鼠的必胜状态。
\n
\n
如果老鼠到达任何节点之后的状态都不是老鼠的必胜状态，但是存在一个节点，老鼠到达该节点之后，结果是平局，则老鼠到达该节点之后的状态为双方的必和状态，因此在老鼠移动之前的当前状态为双方的必和状态。
\n
\n
如果老鼠到达任何节点之后的状态都不是老鼠的必胜状态或必和状态，则老鼠到达任何节点之后的状态都为老鼠的必败状态，猫的必胜状态，因此在老鼠移动之前的当前状态为老鼠的必败状态。
\n

\n

如果轮到猫移动，则对于猫从当前节点移动一次之后可能到达的每个节点，进行如下操作：

\n

\n
如果存在一个节点，猫到达该节点之后，猫可以获胜，则猫到达该节点之后的状态为猫的必胜状态，老鼠的必败状态，因此在猫移动之前的当前状态为猫的必胜状态。
\n
\n
如果猫到达任何节点之后的状态都不是猫的必胜状态，但是存在一个节点，猫到达该节点之后，结果是平局，则猫到达该节点之后的状态为双方的必和状态，因此在猫移动之前的当前状态为双方的必和状态。
\n
\n
如果猫到达任何节点之后的状态都不是猫的必胜状态或必和状态，则猫到达任何节点之后的状态都为猫的必败状态，老鼠的必胜状态，因此在猫移动之前的当前状态为猫的必败状态。
\n

\n

实现方面，由于双方移动的策略相似，因此可以使用一个函数实现移动策略，根据游戏已经进行的轮数的奇偶性决定当前轮到的玩家。对于特定玩家的移动，实现方法如下：

\n

\n
如果当前玩家存在一种移动方法到达非必败状态，则用该状态更新游戏结果。
\n
- \n
  如果该移动方法到达必胜状态，则将当前状态（移动前的状态）设为必胜状态，结束遍历其他可能的移动。
  \n
- \n
  如果该移动方法到达必和状态，则将当前状态（移动前的状态）设为必和状态，继续遍历其他可能的移动，因为可能存在到达必胜状态的移动方法。
  \n
\n
\n
如果当前玩家的任何移动方法都到达必败状态，则将当前状态（移动前的状态）设为必败状态。
\n

\n

由于老鼠可能的位置有 $n$ 个，猫可能的位置有 $n - 1$ 个，游戏轮数最大为 $2n(n - 1)$，因此动态规划的状态数是 $O(n^4)$，对于每个状态需要 $O(n)$ 的时间计算状态值，因此总时间复杂度是 $O(n^5)$，该时间复杂度会超出时间限制，因此自顶向下的动态规划不适用于这道题。以下代码为自顶向下的动态规划的实现，仅供读者参考。

\n

###Java

\n