<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>

class Solution {
public:
    int m_turn = 0, c_turn = 1, M_win = 1, C_win = 2, draw = 0;

    struct Q {
        int m;
        int c;
        int turn;
        int res;
    };

    int catMouseGame(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
        vector<vector<vector<int>>> child(n, vector<vector<int>>(n, vector<int>(2, 0)));

        for (int m = 0; m < n; m++) {
            for (int c = 0; c < n; c++) {
                child[m][c][m_turn] = graph[m].size();  // number of possible next positions for mouse
                child[m][c][c_turn] = graph[c].size();  // number of possible next positions for cat
                for (auto& i : graph[c]) {
                    if (i == 0) {
                        child[m][c][c_turn]--;  // cat will not go to the hole
                        break;
                    }
                }
            }
        }

        // push all the nodes that will definitely win
        queue<Q> q;
        for (int c = 0; c < n; c++) {
            for (int turn = 0; turn <= 1; turn++) {
                dp[0][c][turn] = M_win;  // mouse wins if it reaches the hole
                q.push({0, c, turn, M_win});
                if (c) {  // if not hole
                    dp[c][c][turn] = C_win;  // cat wins if it catches the mouse
                    q.push({c, c, turn, C_win});
                }
            }
        }

        while (!q.empty()) {
            Q p = q.front();  // Copy the element instead of using a reference
            q.pop();
            if (p.m == 1 && p.c == 2 && p.turn == 0)  // we have the result
                return p.res;
            int pre_turn = 1 - p.turn;  // previous turn = 1 - current turn
            for (auto& prev : graph[pre_turn == 0 ? p.m : p.c]) {
                // we know the result of current state, let's find the result for previous turn
                int pre_m = pre_turn == 0 ? prev : p.m;  // previous mouse position
                int pre_c = pre_turn == 1 ? prev : p.c;  // previous cat position
                if (!pre_c) continue;  // cat can't be in the hole
                if (!dp[pre_m][pre_c][pre_turn]) {  // don't know who wins in previous turn, let's find out
                    if ((p.res == 1 && pre_turn == 0) || (p.res == 2 && pre_turn == 1)) {  // whoever has previous turn will win
                        dp[pre_m][pre_c][pre_turn] = p.res;
                        q.push({pre_m, pre_c, pre_turn, p.res});
                    } else {  // whoever has previous turn will lose
                        // this child can't help us win, delete it
                        child[pre_m][pre_c][pre_turn]--;
                        if (!child[pre_m][pre_c][pre_turn]) {  // no child can help us win
                            // whoever has previous turn is guaranteed to lose
                            int result = pre_turn == 0 ? 2 : 1;
                            dp[pre_m][pre_c][pre_turn] = result;  // store the result for previous turn
                            q.push({pre_m, pre_c, pre_turn, result});
                        }
                    }
                }
            }
        }
        return dp[1][2][0];  // return result
    }
};

26925