每日一题——（已摆烂）913. 猫和老鼠

913. 猫和老鼠

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

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：

如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。

public class Solution {
    const int MOUSE_WIN = 1;
    const int CAT_WIN = 2;
    const int DRAW = 0;
    int n;
    int[][] graph;
    int[,,] dp;

    public int CatMouseGame(int[][] graph) {
        this.n = graph.Length;
        this.graph = graph;
        this.dp = new int[n, n, n * 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n * 2; k++) {
                    dp[i, j, k] = -1;
                }
            }
        }
        return GetResult(1, 2, 0);
    }

    public int GetResult(int mouse, int cat, int turns) {
        if (turns == n * 2) {
            return DRAW;
        }
        if (dp[mouse, cat, turns] < 0) {
            if (mouse == 0) {
                dp[mouse, cat, turns] = MOUSE_WIN;
            } else if (cat == mouse) {
                dp[mouse, cat, turns] = CAT_WIN;
            } else {
                GetNextResult(mouse, cat, turns);
            }
        }
        return dp[mouse, cat, turns];
    }

    public void GetNextResult(int mouse, int cat, int turns) {
        int curMove = turns % 2 == 0 ? mouse : cat;
        int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
        int result = defaultResult;
        int[] nextNodes = graph[curMove];
        foreach (int next in nextNodes) {
            if (curMove == cat && next == 0) {
                continue;
            }
            int nextMouse = curMove == mouse ? next : mouse;
            int nextCat = curMove == cat ? next : cat;
            int nextResult = GetResult(nextMouse, nextCat, turns + 1);
            if (nextResult != defaultResult) {
                result = nextResult;
                if (result != DRAW) {
                    break;
                }
            }
        }
        dp[mouse, cat, turns] = result;
    }
}