Skip to content

913. Cat and Mouse

913. Cat and Mouse

题目: https://leetcode.com/problems/cat-and-mouse/

难度: Hard

题意：

  1. 给定一张图，猫和鼠轮流走动，每一次可以走到当前点的下一个节点
  2. 猫胜利的条件是猫和老鼠在同一个位置
  3. 老鼠胜利的条件是到达0号节点
  4. 如果猫和老鼠所到达的状态是先前他们走过的状态，则平局
  5. 猫和鼠都是选择对它们最优的策略走

思路：

  • 零和博弈
  • 轮到猫走的时候，猫会选择一个状态，使得这个状态下猫必胜利
  • 如果找不到一个子状态必胜，那么猫会找一个平局的状态进行游戏
  • 如果找不到一个必胜和一个平局的状态，那么这个状态下只能鼠胜出
  • 轮到鼠走时也是如此
  • 令状态表达式是f[first][cat][mouse]表示猫或者鼠先走时，猫在cat的位置，鼠在mouse的位置的状态，状态值是猫(2)或鼠(1)胜利，或者平局(0)
  • 根据博弈的条件，可以得出状态转移公式和初始状态
  • 这个题最难的地方不在公式，而是无子问题。无法用递推或者递归的方式解决问题。借助一下最短路松弛算法，我们可以从初始状态出发，然后影响周边状态，假设某个状态值改变了，需要对这个状态的周边状态进行重新计算，直到收敛

代码：

class Solution {
    private class Node {
        int first;
        int mouse;
        int cat;

        public Node(int first, int cat, int mouse) {
            this.first = first;
            this.mouse = mouse;
            this.cat = cat;
        }

        public int getFirst() {
            return first;
        }

        public void setFirst(int first) {
            this.first = first;
        }

        public int getMouse() {
            return mouse;
        }

        public void setMouse(int mouse) {
            this.mouse = mouse;
        }

        public int getCat() {
            return cat;
        }

        public void setCat(int cat) {
            this.cat = cat;
        }
    }

    private int solve(int[][] graph) {
        int[][][] cache = new int[2][graph.length][graph.length];
        for (int first = 0;first < 2;first++) {
            for (int cat = 0;cat < graph.length;cat++) {
                for (int mouse = 0;mouse < graph.length;mouse++) {
                    cache[first][cat][mouse] = 0;
                }
            }
        }

        Queue<Node> nodes = new LinkedList<>();

        for (int first = 0;first < 2;first++) {
            for (int cat = 1; cat < graph.length; cat++) {
                for (int mouse = 0; mouse < graph.length; mouse++) {
                    if (mouse == 0) {
                        cache[first][cat][mouse] = 1;
                        nodes.add(new Node(first, cat, mouse));
                    }
                    if (cat == mouse) {
                        cache[first][cat][mouse] = 2;
                        nodes.add(new Node(first, cat, mouse));
                    }
                }
            }
        }

        while (!nodes.isEmpty()) {
            Node node = nodes.poll();

            if (node.first == 0) {
                for (int i = 0;i < graph[node.mouse].length;i++) {
                    int x = graph[node.mouse][i];

                    int pre = cache[1][node.cat][x];
                    if (x == 0 || node.cat == x) {
                        continue;
                    }

                    boolean findWin = false;
                    boolean findDraw = false;
                    for (int j = 0;j < graph[x].length;j++) {
                        int y = graph[x][j];
                        if (cache[0][node.cat][y] == 1) {
                            findWin = true;
                        } else if (cache[0][node.cat][y] == 0) {
                            findDraw = true;
                        }
                    }
                    if (findWin) {
                        cache[1][node.cat][x] = 1;
                    } else if (!findDraw) {
                        cache[1][node.cat][x] = 2;
                    } else {
                        cache[1][node.cat][x] = 0;
                    }

                    if (cache[1][node.cat][x] != pre) {
                        nodes.add(new Node(1, node.cat, x));
                    }
                }
            } else {
                for (int i = 0;i < graph[node.cat].length;i++) {
                    int x = graph[node.cat][i];

                    int pre = cache[0][x][node.mouse];

                    if (x == 0 || node.mouse == x) {
                        continue;
                    }

                    boolean findWin = false;
                    boolean findDraw = false;
                    for (int j = 0;j < graph[x].length;j++) {
                        int y = graph[x][j];
                        if (y == 0) {
                            continue;
                        }
                        if (cache[1][y][node.mouse] == 2) {
                            findWin = true;
                        } else if (cache[1][y][node.mouse] == 0) {
                            findDraw = true;
                        }
                    }
                    if (findWin) {
                        cache[0][x][node.mouse] = 2;
                    } else if (!findDraw) {
                        cache[0][x][node.mouse] = 1;
                    } else {
                        cache[0][x][node.mouse] = 0;
                    }

                    if (pre != cache[0][x][node.mouse]) {
                        nodes.add(new Node(0, x, node.mouse));
                    }
                }
            }
        }

        return cache[1][2][1];
    }

    public int catMouseGame(int[][] graph) {
        int ret = solve(graph);
        return ret;
    }
}
回到顶部