猫和老鼠-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

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

思路：

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

代码：

```java
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;
    }
}
```

该分类下的相关小册推荐：

业务开发实用算法精讲

编程之道-算法面试(下)

数据结构与算法之美

算法面试通关 50 讲

编程之道-算法面试(上)

数据结构与算法(上)

数据结构与算法(下)