<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:
    vector<pair<pair<int, int>, int>>
    getPrevStates(int m, int c, int t, vector<vector<int>>& graph) {
        vector<pair<pair<int, int>, int>> res;
        if (t == 1) {
            for (auto nei : graph[c]) {
                if (nei == 0) {
                    continue;
                }
                res.push_back(make_pair(make_pair(m, nei), 2));
            }
        } else {
            for (auto nei : graph[m]) {
                res.push_back(make_pair(make_pair(nei, c), 1));
            }
        }
        return res;
    }

    bool allNextPathsFail(int m,int c,int t, vector<vector<int>>& graph, vector<vector<vector<int> > >& dp) {
        if(t==1) {
            for(auto nei: graph[m]) {
                if(dp[nei][c][2] != 2) {return false;}
            }
        } else {
            for(auto nei: graph[c]) {
                if(nei == 0){continue;}
                if(dp[m][nei][1] != 1) {return false;}
            }
        }
        return true;
    }
    int catMouseGame(vector<vector<int>>& graph) {
        int n = (int)graph.size();
        queue<pair<pair<int, int>, int>> q;
        vector<vector<vector<int> > > dp(n+1);
        for(int i=0;i<n+1;i++){
            dp[i].resize(n+1);
            for(int j=0;j<n+1;j++) {
                dp[i][j].resize(3);
            }
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                dp[0][j][i] = 1;
                dp[j][j][i] = 2;
                q.push(make_pair(make_pair(0, j), i));
                q.push(make_pair(make_pair(j, j), i));
            }
        }

        while (!q.empty()) {
            auto state = q.front();
            q.pop();
            int m = state.first.first, c = state.first.second, t = state.second;
            int res = dp[m][c][t];
            auto prevStates = getPrevStates(m, c, t, graph);
            for (auto v : prevStates) {
                int m2 = v.first.first, c2 = v.first.second, t2 = v.second;
                int res2 = dp[m2][c2][t2];
                if (res2 > 0) {
                    continue;
                }

                if (t + res == 3) {
                    // gurranted win
                    dp[m2][c2][t2] = res;
                    q.push(make_pair(make_pair(m2, c2), t2));
                } else if (allNextPathsFail(m2, c2, t2, graph, dp)) {
                    dp[m2][c2][t2] = 3 - t2;
                    q.push(make_pair(make_pair(m2, c2), t2));
                }
            }
        }
        return dp[1][2][1];
    }
};
105775