猫和老鼠

913. 猫和老鼠

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

图的形式是：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] 互不相同
猫和老鼠在游戏中总是移动

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int catMouseGame(vector<vector<int>>& graph) { } };

golang 解法, 执行用时: 44 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-25 11:27:32

const (
    mouseTurn = 0
    catTurn   = 1

    draw     = 0
    mouseWin = 1
    catWin   = 2
)

func catMouseGame(graph [][]int) int {
    n := len(graph)
    degrees := make([][][2]int, n)
    results := make([][][2]int, n)
    for i := range degrees {
        degrees[i] = make([][2]int, n)
        results[i] = make([][2]int, n)
    }
    for i, to := range graph {
        for j := 1; j < n; j++ {
            degrees[i][j][mouseTurn] = len(to)
            degrees[i][j][catTurn] = len(graph[j])
        }
    }
    for _, y := range graph[0] {
        for i := range degrees {
            degrees[i][y][catTurn]--
        }
    }

    type state struct{ mouse, cat, turn int }
    q := []state{}
    for j := 1; j < n; j++ {
        results[0][j][mouseTurn] = mouseWin
        results[0][j][catTurn] = mouseWin
        q = append(q, state{0, j, mouseTurn}, state{0, j, catTurn})
    }
    for i := 1; i < n; i++ {
        results[i][i][mouseTurn] = catWin
        results[i][i][catTurn] = catWin
        q = append(q, state{i, i, mouseTurn}, state{i, i, catTurn})
    }

    getPrevStates := func(s state) (prevStates []state) {
        if s.turn == mouseTurn {
            for _, prev := range graph[s.cat] {
                if prev != 0 {
                    prevStates = append(prevStates, state{s.mouse, prev, catTurn})
                }
            }
        } else {
            for _, prev := range graph[s.mouse] {
                prevStates = append(prevStates, state{prev, s.cat, mouseTurn})
            }
        }
        return
    }

    for len(q) > 0 {
        s := q[0]
        q = q[1:]
        result := results[s.mouse][s.cat][s.turn]
        for _, p := range getPrevStates(s) {
            prevMouse, prevCat, prevTurn := p.mouse, p.cat, p.turn
            if results[prevMouse][prevCat][prevTurn] == draw {
                canWin := result == mouseWin && prevTurn == mouseTurn || result == catWin && prevTurn == catTurn
                if canWin {
                    results[prevMouse][prevCat][prevTurn] = result
                    q = append(q, p)
                } else {
                    degrees[prevMouse][prevCat][prevTurn]--
                    if degrees[prevMouse][prevCat][prevTurn] == 0 {
                        if prevTurn == mouseTurn {
                            results[prevMouse][prevCat][prevTurn] = catWin
                        } else {
                            results[prevMouse][prevCat][prevTurn] = mouseWin
                        }
                        q = append(q, p)
                    }
                }
            }
        }
    }
    return results[1][2][mouseTurn]
}

python3 解法, 执行用时: 564 ms, 内存消耗: 16.8 MB, 提交时间: 2023-10-25 11:27:18

MOUSE_TURN = 0
CAT_TURN = 1

DRAW = 0
MOUSE_WIN = 1
CAT_WIN = 2

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]
        results = [[[0, 0] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(1, n):
                degrees[i][j][MOUSE_TURN] = len(graph[i])
                degrees[i][j][CAT_TURN] = len(graph[j])
        for y in graph[0]:
            for i in range(n):
                degrees[i][y][CAT_TURN] -= 1

        q = deque()
        for j in range(1, n):
            results[0][j][MOUSE_TURN] = MOUSE_WIN
            results[0][j][CAT_TURN] = MOUSE_WIN
            q.append((0, j, MOUSE_TURN))
            q.append((0, j, CAT_TURN))
        for i in range(1, n):
            results[i][i][MOUSE_TURN] = CAT_WIN
            results[i][i][CAT_TURN] = CAT_WIN
            q.append((i, i, MOUSE_TURN))
            q.append((i, i, CAT_TURN))

        while q:
            mouse, cat, turn = q.popleft()
            result = results[mouse][cat][turn]
            if turn == MOUSE_TURN:
                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]
            else:
                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]
            for prevMouse, prevCat, prevTurn in prevStates:
                if prevCat == 0:
                    continue
                if results[prevMouse][prevCat][prevTurn] == DRAW:
                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN
                    if canWin:
                        results[prevMouse][prevCat][prevTurn] = result
                        q.append((prevMouse, prevCat, prevTurn))
                    else:
                        degrees[prevMouse][prevCat][prevTurn] -= 1
                        if degrees[prevMouse][prevCat][prevTurn] == 0:
                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN
                            q.append((prevMouse, prevCat, prevTurn))
        return results[1][2][MOUSE_TURN]

java 解法, 执行用时: 58 ms, 内存消耗: 43 MB, 提交时间: 2023-10-25 11:27:02

class Solution {
    static final int MOUSE_TURN = 0, CAT_TURN = 1;
    static final int DRAW = 0, MOUSE_WIN = 1, CAT_WIN = 2;
    int[][] graph;
    int[][][] degrees;
    int[][][] results;

    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        this.graph = graph;
        this.degrees = new int[n][n][2];
        this.results = new int[n][n][2];
        Queue<int[]> queue = new ArrayDeque<int[]>();
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                degrees[i][j][MOUSE_TURN] = graph[i].length;
                degrees[i][j][CAT_TURN] = graph[j].length;
            }
        }
        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;
            queue.offer(new int[]{0, j, MOUSE_TURN});
            queue.offer(new int[]{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;
            queue.offer(new int[]{i, i, MOUSE_TURN});
            queue.offer(new int[]{i, i, CAT_TURN});
        }
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int mouse = state[0], cat = state[1], turn = state[2];
            int result = results[mouse][cat][turn];
            List<int[]> prevStates = getPrevStates(mouse, cat, turn);
            for (int[] prevState : prevStates) {
                int prevMouse = prevState[0], prevCat = prevState[1], prevTurn = prevState[2];
                if (results[prevMouse][prevCat][prevTurn] == DRAW) {
                    boolean canWin = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
                    if (canWin) {
                        results[prevMouse][prevCat][prevTurn] = result;
                        queue.offer(new int[]{prevMouse, prevCat, prevTurn});
                    } else {
                        degrees[prevMouse][prevCat][prevTurn]--;
                        if (degrees[prevMouse][prevCat][prevTurn] == 0) {
                            int loseResult = prevTurn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
                            results[prevMouse][prevCat][prevTurn] = loseResult;
                            queue.offer(new int[]{prevMouse, prevCat, prevTurn});
                        }
                    }
                }
            }
        }
        return results[1][2][MOUSE_TURN];
    }

    public List<int[]> getPrevStates(int mouse, int cat, int turn) {
        List<int[]> prevStates = new ArrayList<int[]>();
        int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
        if (prevTurn == MOUSE_TURN) {
            for (int prev : graph[mouse]) {
                prevStates.add(new int[]{prev, cat, prevTurn});
            }
        } else {
            for (int prev : graph[cat]) {
                if (prev != 0) {
                    prevStates.add(new int[]{mouse, prev, prevTurn});
                }
            }
        }
        return prevStates;
    }
}

上一题

下一题

详情