力扣上的两道猫和老鼠的题目是：

913. 猫和老鼠
1728. 猫和老鼠 II

这两道题都是博弈问题。博弈问题的常见解法是动态规划（包括记忆化搜索），但是这两道题使用动态规划的解法时存在一个问题，即最大步数的判定问题。

对于 913，用 $n$ 表示图中的结点数，判定平局的一个明确步数上界是 $2n(n-1)$。每个状态由老鼠的位置、猫的位置和移动方共同表示，老鼠最多有 $n$ 个不同的位置，猫最多有 $n-1$ 个不同的位置（猫不能进老鼠洞），移动方可能是老鼠或猫，因此不同的状态数是 $2n(n-1)$，根据抽屉原理可知移动 $2n(n-1)$ 次一定会重复经过同一个状态，同一个状态对应的结果相同，因此是平局。

虽然取 $2n(n-1)$ 作为步数上界的动态规划可以得到正确的结果，但是动态规划解法的时间复杂度高达 $O(n^5)$，对于 $n$ 最大为 $50$ 的情况，$O(n^5)$ 的时间复杂度会超时。由此引出一个问题：判定平局的步数上界是否可以取更低的值，例如将步数上界从 $O(n^2)$ 降低到 $O(n)$？如果存在 $O(n)$ 的步数上界，则步数上界和 $n$ 的关系是什么，以及如何证明？

最早的时候认为步数上界取 $2n$ 就足够，但是已经有测试用例证明存在超过 $2n$ 步分出胜负的情况。步数上界取 $3n$、$4n$ 也是不够的，已知当 $n=10$ 时步数上界最大值是 $34$，当 $n=13$ 时存在需要 $58$ 步分出胜负的测试用例，这两个测试用例已经加入到官方测试用例中。但是目前尚未发现分出胜负的步数达到或超过 $5n$ 的情况。

步数上界和结点数之间的倍数关系随着结点数的增加而增加。以下是 $n=3$ 到 $n=10$ 的步数上界以及对应的测试用例。当 $n\le 5$ 时步数上界是奇数，存在老鼠获胜和猫获胜的情况；当 $n\ge 6$ 时步数上界是偶数，一定是猫获胜。

$n=3$，步数上界是 $1$：

[[1,2],[0,2],[0,1]]
[[2],[2],[0,1]]

$n=4$，步数上界是 $3$：

[[3],[2,3],[1],[0,1]]
[[2],[2,3],[0,1],[1]]

$n=5$，步数上界是 $5$：

[[3],[2,4],[1],[0,4],[1,3]]
[[3],[4],[3],[0,2,4],[1,3]]

$n=6$，步数上界是 $8$：

[[3],[2,4,5],[1,3],[0,2,4,5],[1,3,5],[1,3,4]]

$n=7$，步数上界是 $12$：

[[3],[2,4,5,6],[1,5],[0,4,5,6],[1,3,6],[1,2,3],[1,3,4]]

$n=8$，步数上界是 $16$：

[[3],[4,5,6],[5,6],[0,6,7],[1,6,7],[1,2,7],[1,2,3,4],[3,4,5]]

$n=9$，步数上界是 $24$：

[[3],[2,5,6],[1,4,7,8],[0,4,5,6],[2,3,8],[1,3,6],[1,3,5,7,8],[2,6,8],[2,4,6,7]]

$n=10$，步数上界是 $34$：

[[3],[5,6,8],[4,5,7],[0,5,6,9],[2,7,8],[1,2,3,7],[1,3,8,9],[2,4,5,9],[1,4,6,9],[3,6,7,8]]

当 $n>10$ 时应该存在更大的步数上界，但是随着 $n$ 的增加，回溯需要的时间呈指数级增加，通过回溯枚举所有可能的测试用例非常不现实。

对于 1728，用 $m$ 和 $n$ 表示矩阵的行数和列数（原题用 $\text{rows}$ 和 $\text{cols}$ 表示矩阵的行数和列数，此处为了简化因此用 $m$ 和 $n$ 表示）。在不考虑老鼠必须在 $1000$ 步获胜的限制下，根据上述分析可知判定平局的一个明确步数上界是 $2m^2{n}^2$，由于 $m$ 和 $n$ 的最大值都是 $8$，因此 $2m^2{n}^2$ 的最大值是 $8192$，超过 $1000$ 步。部分题解取了较低的步数上界使用动态规划求解，例如将步数上界取为 $2mn$，虽然可以通过，但是这个步数上界未必正确。

由于矩阵和普通的图有所区别，因此实际需要的最大步数应该小于 $2m^2{n}^2$，但是是否一定小于 $1000$？一个同样的问题是：判定平局的步数上界是多少，以及如何证明？

对于这两道题，请扣友共同思考，尝试找到可以分出胜负的最大步数，并构造出可以分出胜负的最大步数的测试用例。