力扣LeetCode: 913 猫和老鼠

发布于：2025-02-11 ⋅ 阅读:(148) ⋅ 点赞:(0)

题目：

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

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

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

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

此外，猫无法移动到洞中（节点 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 <= graph.length <= 50
  • 1 <= graph[i].length < graph.length
  • 0 <= graph[i][j] < graph.length
  • graph[i][j] != i
  • graph[i] 互不相同
  • 猫和老鼠在游戏中总是可以移动

解法：拓扑排序（解释官方题解）

有点难！

代码思路

这个代码使用了博弈论中的极小化极大算法，并结合了拓扑排序的思想。具体来说，代码通过以下步骤来解决问题：

  1. 初始化：

    • 定义了一些常量，如 HOLE、MOUSE_START、CAT_START 等。

    • 定义了一个 Solution 类，其中包含了主要的 catMouseGame 函数。

  2. 图的表示：

    • 使用 graph 表示图的邻接表，graph[i] 表示节点 i 的相邻节点。

  3. 状态的定义：

    • 使用 degrees 数组来记录每个状态的“出度”，即从当前状态可以转移到多少个其他状态。

    • 使用 results 数组来记录每个状态的结果（UNKNOWN、MOUSE_WIN、CAT_WIN）。

  4. 初始化状态：

    • 对于所有 mouse == cat 的状态，猫获胜，因为猫抓到了老鼠。

    • 对于所有 mouse == HOLE 的状态，老鼠获胜，因为老鼠成功逃脱。

    • 将这些已知结果的状态加入队列 q 中，用于后续的广度优先搜索（BFS）。

  5. 广度优先搜索（BFS）：

    • 从已知结果的状态开始，逐步推导其他状态的结果。

    • 对于每个状态，检查它的前驱状态（即可以从哪些状态转移到当前状态）。

    • 如果前驱状态的结果尚未确定，则根据当前状态的结果来更新前驱状态的结果。

    • 如果某个前驱状态的所有后继状态都已经确定，则该前驱状态的结果也可以确定。

  6. 返回结果：

    • 最终返回初始状态 (MOUSE_START, CAT_START, MOUSE_TURN) 的结果。

class Solution {
public:
    const int MOUSE_TURN = 0, CAT_TURN = 1;
    const int DRAW = 0, MOUSE_WIN = 1, CAT_WIN = 2;
    vector<vector<int>> graph;
    vector<vector<vector<int>>> degrees;
    vector<vector<vector<int>>> results;

    int catMouseGame(vector<vector<int>>& graph) {
        int n = graph.size();
        this->graph = graph;
        this->degrees = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(2)));
        this->results = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(2)));
        queue<tuple<int, int, int>> qu;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                degrees[i][j][MOUSE_TURN] = graph[i].size();
                degrees[i][j][CAT_TURN] = graph[j].size();
            }
        }
        for (int node : graph[0]) {
            for (int i = 0; i < n; i++) {
                degrees[i][node][CAT_TURN]--;
            }
        }
        for (int j = 1; j < n; j++) {
            results[0][j][MOUSE_TURN] = MOUSE_WIN;
            results[0][j][CAT_TURN] = MOUSE_WIN;
            qu.emplace(0, j, MOUSE_TURN);
            qu.emplace(0, j, CAT_TURN);
        }
        for (int i = 1; i < n; i++) {
            results[i][i][MOUSE_TURN] = CAT_WIN;
            results[i][i][CAT_TURN] = CAT_WIN;
            qu.emplace(i, i, MOUSE_TURN);
            qu.emplace(i, i, CAT_TURN);
        }
        while (!qu.empty()) {
            auto [mouse, cat, turn] = qu.front();
            qu.pop();
            int result = results[mouse][cat][turn];
            vector<tuple<int, int, int>> prevStates = GetPrevStates(mouse, cat, turn);
            for (auto & [prevMouse, prevCat, prevTurn] : prevStates) {
                if (results[prevMouse][prevCat][prevTurn] == DRAW) {
                    bool canWin = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
                    if (canWin) {
                        results[prevMouse][prevCat][prevTurn] = result;
                        qu.emplace(prevMouse, prevCat, prevTurn);
                    } else if (--degrees[prevMouse][prevCat][prevTurn] == 0) {
                        int loseResult = prevTurn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
                        results[prevMouse][prevCat][prevTurn] = loseResult;
                        qu.emplace(prevMouse, prevCat, prevTurn);
                    }
                }
            }
        }
        return results[1][2][MOUSE_TURN];
    }

    vector<tuple<int, int, int>> GetPrevStates(int mouse, int cat, int turn) {
        vector<tuple<int, int, int>> prevStates;
        int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
        if (prevTurn == MOUSE_TURN) {
            for (int & prev : graph[mouse]) {
                prevStates.emplace_back(prev, cat, prevTurn);
            }
        } else {
            for (int & prev : graph[cat]) {
                if (prev != 0) {
                    prevStates.emplace_back(mouse, prev, prevTurn);
                }
            }
        }
        return prevStates;
    }
};

代码详细解释

1. 常量和变量定义
const int HOLE = 0, MOUSE_START = 1, CAT_START = 2;
const int MOUSE_TURN = 0, CAT_TURN = 1;
const int UNKNOWN = 0, MOUSE_WIN = 1, CAT_WIN = 2;

  • HOLE 表示老鼠的目标节点。

  • MOUSE_START 和 CAT_START 分别表示老鼠和猫的起始节点。

  • MOUSE_TURN 和 CAT_TURN 表示当前是老鼠还是猫的回合。

  • UNKNOWN、MOUSE_WIN、CAT_WIN 表示当前状态的结果。

2. catMouseGame 函数
int catMouseGame(vector<vector<int>>& graph) {
    this->n = graph.size();
    this->graph = graph;
    this->degrees = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(2)));
    this->results = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(2)));

  • n 是图的节点数。

  • degrees 是一个三维数组，degrees[mouse][cat][turn] 表示从状态 (mouse, cat, turn) 可以转移到多少个其他状态。

  • results 是一个三维数组，results[mouse][cat][turn] 表示状态 (mouse, cat, turn) 的结果。

3. 初始化 degrees 数组
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j++) {
        degrees[i][j][MOUSE_TURN] = graph[i].size();
        degrees[i][j][CAT_TURN] = graph[j].size();
    }
}

  • 对于每个状态 (mouse, cat, MOUSE_TURN)，degrees[mouse][cat][MOUSE_TURN] 初始化为老鼠可以移动的节点数。

  • 对于每个状态 (mouse, cat, CAT_TURN)，degrees[mouse][cat][CAT_TURN] 初始化为猫可以移动的节点数。

4. 处理 HOLE 节点
for (int i = 0; i < n; i++) {
    for (int j : graph[HOLE]) {
        degrees[i][j][CAT_TURN]--;
    }
}

  • 如果猫可以移动到 HOLE，则减少 degrees[i][j][CAT_TURN]，因为猫不能移动到 HOLE。

5. 初始化已知结果的状态
queue<tuple<int, int, int>> q;
for (int i = 1; i < n; i++) {
    results[i][i][MOUSE_TURN] = CAT_WIN;
    results[i][i][CAT_TURN] = CAT_WIN;
    q.emplace(i, i, MOUSE_TURN);
    q.emplace(i, i, CAT_TURN);
}
for (int j = 1; j < n; j++) {
    results[HOLE][j][MOUSE_TURN] = MOUSE_WIN;
    results[HOLE][j][CAT_TURN] = MOUSE_WIN;
    q.emplace(HOLE, j, MOUSE_TURN);
    q.emplace(HOLE, j, CAT_TURN);
}

  • 对于所有 mouse == cat 的状态，猫获胜。

  • 对于所有 mouse == HOLE 的状态，老鼠获胜。

  • 将这些状态加入队列 q 中。

6. 广度优先搜索（BFS）
while (!q.empty()) {
    tuple<int, int, int> state = q.front();
    q.pop();
    int mouse = get<0>(state), cat = get<1>(state), turn = get<2>(state);
    int result = results[mouse][cat][turn];
    vector<tuple<int, int, int>> prevStates = getPrevStates(mouse, cat, turn);
    for (tuple<int, int, int> prevState : prevStates) {
        int prevMouse = get<0>(prevState), prevCat = get<1>(prevState), prevTurn = get<2>(prevState);
        if (results[prevMouse][prevCat][prevTurn] == UNKNOWN) {
            bool winState = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
            if (winState) {
                results[prevMouse][prevCat][prevTurn] = result;
                q.emplace(prevMouse, prevCat, prevTurn);
            } else {
                degrees[prevMouse][prevCat][prevTurn]--;
                if (degrees[prevMouse][prevCat][prevTurn] == 0) {
                    results[prevMouse][prevCat][prevTurn] = result;
                    q.emplace(prevMouse, prevCat, prevTurn);
                }
            }
        }
    }
}

  • 从队列 q 中取出一个状态 (mouse, cat, turn)。

  • 获取该状态的结果 result。

  • 获取该状态的前驱状态 prevStates。

  • 对于每个前驱状态，如果结果尚未确定：

    • 如果当前状态的结果是 MOUSE_WIN 且前驱状态是老鼠的回合，或者当前状态的结果是 CAT_WIN 且前驱状态是猫的回合，则前驱状态的结果可以确定为当前状态的结果。

    • 否则，减少前驱状态的 degrees，如果 degrees 减为 0，则前驱状态的结果可以确定为当前状态的结果。

7. 返回结果
return results[MOUSE_START][CAT_START][MOUSE_TURN];

  • 返回初始状态 (MOUSE_START, CAT_START, MOUSE_TURN) 的结果。

总结

这个代码通过广度优先搜索（BFS）和拓扑排序的思想，逐步推导出每个状态的结果，最终确定初始状态的结果。通过这种方式，可以有效地解决“猫和老鼠”游戏的问题。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布