913. Cat and Mouse

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0.

During each player’s turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0).

Then, the game can end in three ways:

• If ever the Cat occupies the same node as the Mouse, the Cat wins.
• If ever the Mouse reaches the Hole, the Mouse wins.
• If ever a position is repeated (i.e., the players are in the same position as a previous turn, and it is the same player’s turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return

• 1 if the mouse wins the game,
• 2 if the cat wins the game, or
• 0 if the game is a draw.
   

Example 1:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

Example 2:

Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1

Constraints:

• 3 <= graph.length <= 50
• 1 <= graph[i].length < graph.length
• 0 <= graph[i][j] < graph.length
• graph[i][j] != i
• graph[i] is unique.
• The mouse and the cat can always move.

From: LeetCode
Link: 913. Cat and Mouse

Solution:

Ideas:

• Model each state as (mouse, cat, turn).

• color[state] is the resolved outcome (0 draw/unknown, 1 mouse win, 2 cat win).

• degree[state] counts legal moves for the side to play (cat cannot go to node 0).

• Seed terminal states:

  • Mouse at 0 → Mouse wins.

  • Mouse and Cat on same node (≠0) → Cat wins.

• BFS backward:

  • If a parent side can move to a child that’s winning for itself, color the parent as a win.

  • Otherwise, decrement the parent’s remaining moves; if they all lead to the opponent’s win, color the parent as a loss (opponent’s win).

• Return the color of the initial state (1,2,mouseTurn).

Code:

typedef struct {
    int m, c, t; // mouse node, cat node, turn (0=mouse,1=cat)
} Node;

static inline int idx(int n, int m, int c, int t) {
    return (((m * n) + c) << 1) | t; // linearize (m,c,t)
}

/*
 * graph: adjacency lists
 * graphSize: n
 * graphColSize[i]: degree of node i
 */
int catMouseGame(int** graph, int n, int* graphColSize) {
    const int MOUSE = 1, CAT = 2; // colors/outcomes we store
    const int DRAW  = 0;

    int states = n * n * 2;

    // color[s] in {0 draw/unknown, 1 mouse win, 2 cat win}
    int *color = (int*)calloc(states, sizeof(int));

    // degree[s]: remaining legal options for the player to move in state s
    int *degree = (int*)malloc(states * sizeof(int));

    // Precompute cat degree per node (can't move into 0)
    int *catDeg = (int*)malloc(n * sizeof(int));
    for (int c = 0; c < n; ++c) {
        int d = 0;
        for (int k = 0; k < graphColSize[c]; ++k)
            if (graph[c][k] != 0) ++d;
        catDeg[c] = d;
    }

    // Initialize degrees for every (m,c,t)
    for (int m = 0; m < n; ++m) {
        for (int c = 0; c < n; ++c) {
            degree[idx(n, m, c, 0)] = graphColSize[m]; // mouse moves
            degree[idx(n, m, c, 1)] = catDeg[c];       // cat moves (no 0)
        }
    }

    // Simple queue for BFS
    Node *q = (Node*)malloc(states * sizeof(Node));
    int qh = 0, qt = 0;

    // Base states:
    // 1) Mouse at hole -> mouse wins, both turns
    for (int c = 0; c < n; ++c) {
        for (int t = 0; t < 2; ++t) {
            int s = idx(n, 0, c, t);
            if (color[s] == DRAW) {
                color[s] = MOUSE;
                q[qt++] = (Node){0, c, t};
            }
        }
    }
    // 2) Cat catches mouse (m == c != 0) -> cat wins, both turns
    for (int x = 1; x < n; ++x) {
        for (int t = 0; t < 2; ++t) {
            int s = idx(n, x, x, t);
            if (color[s] == DRAW) {
                color[s] = CAT;
                q[qt++] = (Node){x, x, t};
            }
        }
    }

    // Helper lambdas (C-style) to iterate parents of a state
    // If state has turn t, parents have turn 1-t and moved into this state.
    while (qh < qt) {
        Node cur = q[qh++]; // resolved state
        int m = cur.m, c = cur.c, t = cur.t;
        int cur_color = color[idx(n, m, c, t)];

        // Generate parents
        if (t == 0) {
            // It's mouse's turn in current -> parents were CAT's turn and cat moved.
            for (int k = 0; k < graphColSize[c]; ++k) {
                int pc = graph[c][k];
                if (pc == 0) continue; // cat can't come from 0
                int pm = m;
                int pt = 1; // cat to move in parent
                int ps = idx(n, pm, pc, pt);
                if (color[ps] != DRAW) continue;

                // If parent player can move to a state that is winning for itself, mark parent accordingly
                if (cur_color == CAT) {
                    // Cat can choose this move -> parent becomes CAT win
                    color[ps] = CAT;
                    q[qt++] = (Node){pm, pc, pt};
                } else {
                    // Otherwise, reduce degree; if no safe moves left, parent becomes opponent win
                    if (--degree[ps] == 0) {
                        color[ps] = MOUSE; // all children are mouse-win -> parent (cat turn) loses -> mouse win
                        q[qt++] = (Node){pm, pc, pt};
                    }
                }
            }
        } else {
            // It's cat's turn in current -> parents were MOUSE's turn and mouse moved.
            for (int k = 0; k < graphColSize[m]; ++k) {
                int pm = graph[m][k];
                int pc = c;
                int pt = 0; // mouse to move in parent
                int ps = idx(n, pm, pc, pt);
                if (color[ps] != DRAW) continue;

                if (cur_color == MOUSE) {
                    // Mouse can choose winning move -> parent becomes MOUSE win
                    color[ps] = MOUSE;
                    q[qt++] = (Node){pm, pc, pt};
                } else {
                    if (--degree[ps] == 0) {
                        color[ps] = CAT; // all children are cat-win -> parent (mouse turn) loses -> cat win
                        q[qt++] = (Node){pm, pc, pt};
                    }
                }
            }
        }
    }

    int result = color[idx(n, 1, 2, 0)]; // start: mouse=1, cat=2, mouse to move
    free(q);
    free(degree);
    free(color);
    free(catDeg);
    return result; // 1=mouse, 2=cat, 0=draw
}