913.猫和老鼠

猫和老鼠

两位玩家分别扮演猫和老鼠，在一张无向图上进行游戏，他们轮流行动。

老鼠从节点 1 开始出发，猫从节点 2 开始出发。

无向图共有 n 个节点，从 1 到 n 编号。图用一个二维矩阵 graph 表示，其中 graph[i] 是一个列表，代表节点 i 连接的所有节点。

老鼠移动到相邻的节点，猫也可以移动到相邻的节点，但不能进入节点 0（老鼠洞）。

如果老鼠到达节点 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

提示：

• 3 <= n <= 50
• graph[i] 是一个列表，包含节点 i 的所有相邻节点（没有重复边）
• graph[i] 不包含 i
• 如果 j 在 graph[i] 中，则 i 也在 graph[j] 中
• 输入的图保证连通

解析

使用博弈论 DP，状态为 (mousePos, catPos, turn)，turn 表示轮到谁行动（0=老鼠，1=猫）。使用记忆化搜索判断每个状态的胜负。

var catMouseGame = function (graph) {
  const n = graph.length;
  const memo = new Map();

  function dfs(mouse, cat, turn) {
    const key = `${mouse},${cat},${turn}`;
    if (memo.has(key)) return memo.get(key);

    // 老鼠进洞，老鼠胜
    if (mouse === 0) return 1;
    // 猫抓到老鼠，猫胜
    if (mouse === cat) return 2;
    // 超过2n步，平局
    const steps = (mouse * n + cat) * 2 + turn;
    if (steps >= 2 * n * n) return 0;

    let result;
    if (turn === 0) {
      // 老鼠回合，寻找必胜或平局
      result = 2; // 先假设最坏情况
      for (const next of graph[mouse]) {
        const r = dfs(next, cat, 1);
        if (r === 1) {
          result = 1;
          break;
        }
        if (r === 0) result = 0;
      }
    } else {
      // 猫回合
      result = 1;
      for (const next of graph[cat]) {
        if (next === 0) continue; // 猫不能进洞
        const r = dfs(mouse, next, 0);
        if (r === 2) {
          result = 2;
          break;
        }
        if (r === 0) result = 0;
      }
    }

    memo.set(key, result);
    return result;
  }

  return dfs(1, 2, 0);
};

时间复杂度 O(n³)，空间复杂度 O(n²)。