算法笔记之博弈问题——猫和老鼠

博弈问题，需要注意，对于每个玩家，都会争取：

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

题目描述

LeetCode913. 猫和老鼠

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

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

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

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

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

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

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

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

解题思路

题目描述比较长，但其实还是很好理解的。需要注意，每个玩家都会争取自己获胜。本题就是简单的深度优先搜素+记忆化问题了。

这里考虑的是怎么才能算平局，我们采取的方法是，如果有n个节点，到2n轮如果还没出结果，就认为可以平局了。

需要注意的是记忆化，memo[i][j][k] 代表猫在i，老鼠在j，在第k轮的结果。

Java代码

class Solution {
    private int[][][] memo; // 记忆化
    private int n;
    private int[][] graph;
    public int catMouseGame(int[][] graph) {
        n = graph.length;
        memo = new int[n][n][n * 2];
        this.graph = graph;
        for(int i = 0; i < memo.length; i++) {
            for(int j = 0; j < memo[i].length; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return dfs(2, 1, 0);
    }

    private int dfs(int catPos, int mousePos, int turn) {
        if(mousePos == 0) {
            return 1; // 老鼠赢
        } else if(catPos == mousePos) {
            return 2; // 猫赢返回1
        }

        if(turn >= 2 * n) {
            return 0; // 已经走完两轮，平局了
        }

        if(memo[catPos][mousePos][turn] != -1) {
            return memo[catPos][mousePos][turn];
        }

        if(turn % 2 == 0) { // 老鼠行动
            boolean canWin = false; // 是否能赢
            boolean canDraw = false;  // 是否能平
            for(int i = 0; i < graph[mousePos].length; i++) {
                int r = dfs(catPos, graph[mousePos][i], turn + 1);
                
                if(r == 1) { // 找自己能赢的路线
                    canWin = true;
                    break;
                } else if(r == 0) {
                    canDraw = true;
                }
            }
            if(canWin) {
                memo[catPos][mousePos][turn] = 1;
                return 1;
            } else if(canDraw) {
                memo[catPos][mousePos][turn] = 0;
                return 0;
            } else {
                memo[catPos][mousePos][turn] = 2;
                return 2;
            }
        } else { // 猫行动
            boolean canWin = false; // 是否能赢
            boolean canDraw = false;  // 是否能平
            for(int i = 0; i < graph[catPos].length; i++) {
                // 猫不能去0
                if(graph[catPos][i] == 0) {
                    continue;
                }
                int r = dfs(graph[catPos][i], mousePos, turn + 1);
                
                if(r == 2) { // 找自己能赢的路线
                    canWin = true;
                    break;
                } else if(r == 0) {
                    canDraw = true;
                }
            }
            if(canWin) {
                memo[catPos][mousePos][turn] = 2;
                return 2;
            } else if(canDraw) {
                memo[catPos][mousePos][turn] = 0;
                return 0;
            } else {
                memo[catPos][mousePos][turn] = 1;
                return 1;
            }
        }
    }
}