搜索
1.4 猫和老鼠
记忆化DFS。
【比赛结束条件】 平局:轮数>=2n；老鼠赢:老鼠的位置为0；猫赢:猫的位置==老鼠的位置。
老鼠赢/猫赢非常好理解；至于为什么轮数>=2n时为平局（陷入僵局），非常巧妙：
如果游戏已经进行了 2n 轮，但是仍然没有任何一方获胜，此时猫和老鼠各移动了 n 次，该移动次数等于图中的节点数，因此一定存在一个老鼠到达过至少两次的节点，以及一定存在一个猫到达过至少两次的节点（不能以双方肯定平局为前提，计算出(n-1)+(n-1)=2n-2轮）。
对于老鼠而言，即使按照最优策略，也无法躲入洞内，而是只能回到一个已经到达过的节点。当老鼠回到一个在过去的某个回合已经到达过的节点时，猫可能回到在相同回合已经到达过的节点，也可能移动到一个更有利于猫获胜的节点，不可能移动到一个更有利于老鼠获胜的节点（否则猫就不是按照最优策略参与游戏）。如果猫回到在相同回合已经到达过的节点，则形成循环，因此是平局；如果猫移动到一个更有利于猫获胜的节点，则老鼠的获胜机会更小，因此老鼠无法获胜。
同理可知，如果猫按照最优策略也只能回到一个已经到达过的节点，则猫无法获胜。
因此当猫和老鼠分别回到一个已经到达过的节点时，猫和老鼠都无法获胜，游戏结果是平局。
对于给定的图，给定了猫和老鼠的起始位置后，哪怕猫和老鼠每一步都以绝对理性进行（博弈论），输赢是从一开始就定下的。若猫当前位置为i/老鼠当前位置为j，则设res(i,j)为最终结果。对于满足让比赛结束的条件，可以直接判定res(i,j)的结果；对于还需要继续比赛的情况，其一条路上的res是相同的，故可以用dfs搜索一条路上最后的结果，并将整条路都标记为这一结果。由于res(i,j)是固定的，我们设一数组memo(i,j)来存储这一结果，减少搜索次数。
当然，从某一起点起，沿着不同道路可以到达不同的结果。猫和鼠双方的任务都是寻求一条结果最好的路径，所以需要对每一条可能的路径都进行搜索。
由于该题存在“平局”的状态，比赛结果与进行的轮次有关，固在原有memo(i,j)的基础上新增轮次维度——>memo(i,j,k)。进行dfs搜索时，memo( , ,k)与相邻的memo( , ,k+1)结果相同。
