Implementation Pattern

Here is the minimax game state implementation:

function catMouseGame(graph, n):
    // States: (mouse_pos, cat_pos, turn)
    // 0 = draw, 1 = mouse wins, 2 = cat wins
    MOUSE = 1
    CAT = 2

    result = 3D array of size n x n x 2, all 0
    degree = 3D array tracking remaining moves

    // Initialize winning states
    queue = empty
    for cat from 1 to n - 1:
        // Cat at hole (0) is impossible
        result[0][cat][MOUSE] = MOUSE  // mouse at hole wins
        result[0][cat][CAT] = MOUSE
        queue.push((0, cat, MOUSE))
        queue.push((0, cat, CAT))

    for pos from 1 to n - 1:
        result[pos][pos][MOUSE] = CAT  // same position = cat wins
        result[pos][pos][CAT] = CAT
        queue.push((pos, pos, MOUSE))
        queue.push((pos, pos, CAT))

    // Backwards BFS to propagate results
    while queue is not empty:
        (mouse, cat, turn) = queue.pop()
        winner = result[mouse][cat][turn]

        // Find parents: states that could move here
        for each parent state (pm, pc, pt):
            if result[pm][pc][pt] != 0:
                continue
            // If parent can guarantee a win, propagate
            if canPropagate(parent, winner):
                result[pm][pc][pt] = winner
                queue.push((pm, pc, pt))

    return result[1][2][MOUSE]

Time: $O(n^3)$. Space: $O(n^2)$.