<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 {
private:
    vector<vector<vector<vector<int>>>> dp;

public:
    int catMouseGame(vector<vector<int>>& graph) {
        int n = graph.size();
        dp.resize(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(2, vector<int>(3 * n + 1, -1))));
        return catMouseBothMove(graph, 1, 2, 0, 0);
    }

    // @turn : 0 - mouse, 1 - cat
    int catMouseBothMove(vector<vector<int>>& graph, int mouse, int cat, int turn, int totalTurns) {
        int n = graph.size();
        
        // End Case 1: If total moves exceed a threshold (draw)
        if (totalTurns == n * 3) return 0;
        
        // End Case 2: If the game reaches initial state again after moves, it's a draw
        if (mouse == 1 && cat == 2 && turn == 0 && totalTurns > 0) return 0;
        
        // End Case 3: If the mouse reaches the hole, mouse wins
        if (mouse == 0 && turn == 1) return 1;
        
        // End Case 4: If the cat catches the mouse, cat wins
        if (turn == 0 && cat == mouse) return 2;

        // If the result has been memoized, return it
        if (dp[mouse][cat][turn][totalTurns] != -1) return dp[mouse][cat][turn][totalTurns];
        
        int result;
        
        // Mouse's turn (turn == 0)
        if (turn == 0) {
            result = 2;  // Assume worst case, cat wins
            for (int v : graph[mouse]) {
                if (v != cat) {
                    int res = catMouseBothMove(graph, v, cat, 1, totalTurns);
                    if (res == 1) {  // If mouse wins, stop early
                        result = 1;
                        break;
                    }
                    if (res == 0) {  // If a draw is possible, keep track
                        result = 0;
                    }
                }
            }
        } 
        // Cat's turn (turn == 1)
        else {
            result = 1;  // Assume worst case, mouse wins
            for (int v : graph[cat]) {
                if (v != 0) {  // Cat can't move to the hole
                    int res = catMouseBothMove(graph, mouse, v, 0, totalTurns + 1);
                    if (res == 2) {  // If cat wins, stop early
                        result = 2;
                        break;
                    }
                    if (res == 0) {  // If a draw is possible, keep track
                        result = 0;
                    }
                }
            }
        }

        // Memoize the result and return it
        return dp[mouse][cat][turn][totalTurns] = result;
    }
};

122375