<p>A game on an <strong>undirected</strong> graph is played by two players, Mouse and Cat, who alternate turns.</p>

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

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

<p>During each player&#39;s turn, they <strong>must</strong> travel along one&nbsp;edge of the graph that meets where they are.&nbsp; For example, if the Mouse is at node 1, it <strong>must</strong> travel to any node in <code>graph[1]</code>.</p>

<p>Additionally, it is not allowed for the Cat to travel to the Hole (node <code>0</code>).</p>

<p>Then, the game can end in three&nbsp;ways:</p>

<ul>
	<li>If ever the Cat occupies the same node as the Mouse, the Cat wins.</li>
	<li>If ever the Mouse reaches the Hole, the Mouse wins.</li>
	<li>If ever a position is repeated (i.e., the players are in the same position as a previous turn, and&nbsp;it is the same player&#39;s turn to move), the game is a draw.</li>
</ul>

<p>Given a <code>graph</code>, and assuming both players play optimally, return</p>

<ul>
	<li><code>1</code>&nbsp;if the mouse wins the game,</li>
	<li><code>2</code>&nbsp;if the cat wins the game, or</li>
	<li><code>0</code>&nbsp;if the game is a draw.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/17/cat1.jpg" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/17/cat2.jpg" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> graph = [[1,3],[0],[3],[0,2]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= graph.length &lt;= 50</code></li>
	<li><code>1&nbsp;&lt;= graph[i].length &lt; graph.length</code></li>
	<li><code>0 &lt;= graph[i][j] &lt; graph.length</code></li>
	<li><code>graph[i][j] != i</code></li>
	<li><code>graph[i]</code> is unique.</li>
	<li>The mouse and the cat can always move.&nbsp;</li>
</ul>

from collections import deque

# Constants to improve readability.
HOLE = 0
MOUSE_START = 1
CAT_START = 2
MOUSE_TURN = 0
CAT_TURN = 1
MOUSE_WIN = 1
CAT_WIN = 2
DRAW = 0

class Solution:
    def catMouseGame(self, graph):
        nodes_count = len(graph)
        # Initialize results and degrees for dynamic programming.
        result = [[[DRAW] * 2 for _ in range(nodes_count)] for _ in range(nodes_count)]
        degrees = [[[0] * 2 for _ in range(nodes_count)] for _ in range(nodes_count)]

        # Initialize the degrees and result matrices.
        for mouse_pos in range(nodes_count):
            for cat_pos in range(1, nodes_count):
                degrees[mouse_pos][cat_pos][MOUSE_TURN] = len(graph[mouse_pos])
                degrees[mouse_pos][cat_pos][CAT_TURN] = len(graph[cat_pos]) - graph[cat_pos].count(HOLE)

        # Helper function to get previous states for mouse and cat turns.
        def get_prev_states(mouse_pos, cat_pos, turn):
            previous_states = []
            prev_turn = 1 - turn  # Toggle turn
            if prev_turn == CAT_TURN:
                # Possible positions for the cat's previous turn.
                for prev_cat_pos in graph[cat_pos]:
                    if prev_cat_pos != HOLE:
                        previous_states.append((mouse_pos, prev_cat_pos, prev_turn))
            else:
                # Possible positions for the mouse's previous turn.
                for prev_mouse_pos in graph[mouse_pos]:
                    previous_states.append((prev_mouse_pos, cat_pos, prev_turn))
            return previous_states

        # Queue for processing states using BFS.
        states_queue = deque()

        # Initialize the queue with base cases where the game is already decided.
        for i in range(1, nodes_count):
            result[HOLE][i][MOUSE_TURN] = result[HOLE][i][CAT_TURN] = MOUSE_WIN
            states_queue.append((HOLE, i, MOUSE_TURN))
            states_queue.append((HOLE, i, CAT_TURN))

            result[i][i][MOUSE_TURN] = result[i][i][CAT_TURN] = CAT_WIN
            states_queue.append((i, i, MOUSE_TURN))
            states_queue.append((i, i, CAT_TURN))

        # Process the queue using BFS to determine the rest of the game states.
        while states_queue:
            mouse_pos, cat_pos, turn = states_queue.popleft()
            curr_result = result[mouse_pos][cat_pos][turn]

            # Evaluate all previous states.
            for prev_mouse_pos, prev_cat_pos, prev_turn in get_prev_states(mouse_pos, cat_pos, turn):
                # If the outcome has not been determined for this state.
                if result[prev_mouse_pos][prev_cat_pos][prev_turn] == DRAW:
                    can_win = (curr_result == MOUSE_WIN and prev_turn == MOUSE_TURN) or (curr_result == CAT_WIN and prev_turn == CAT_TURN)
                    if can_win:
                        # Update the state directly if we know it leads to a win.
                        result[prev_mouse_pos][prev_cat_pos][prev_turn] = curr_result
                        states_queue.append((prev_mouse_pos, prev_cat_pos, prev_turn))
                    else:
                        # Decrement the degree and check if we can conclude the result.
                        degrees[prev_mouse_pos][prev_cat_pos][prev_turn] -= 1
                        if degrees[prev_mouse_pos][prev_cat_pos][prev_turn] == 0:
                            result[prev_mouse_pos][prev_cat_pos][prev_turn] = curr_result
                            states_queue.append((prev_mouse_pos, prev_cat_pos, prev_turn))

        # Return the result for the starting state of the game.
        return result[MOUSE_START][CAT_START][MOUSE_TURN]

17300