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

// https://leetcode.cn/problems/cat-and-mouse/solutions/1685386/by-stormsunshine-k6fn/
class Solution {


public:
    int catMouseGame(std::vector<std::vector<int>>& graph) {
        static constexpr int HOLE = 0, MOUSE_START = 1, CAT_START = 2;
        static constexpr int MOUSE_TURN = 0, CAT_TURN = 1;
        static constexpr int UNKNOWN = 0, MOUSE_WIN = 1, CAT_WIN = 2;

        int n = graph.size();

        std::vector<std::vector<std::vector<int>>> degree(n, std::vector<std::vector<int>>(n, std::vector<int>(2)));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                degree[i][j][MOUSE_TURN] = graph[i].size();
                degree[i][j][CAT_TURN] = graph[j].size();
            }
        }
        for (int i = 0; i < n; ++i) {
            for (auto j : graph[HOLE]) {
                --degree[i][j][CAT_TURN];
            }
        }

        auto getPrevStates = [&graph] (int mouse, int cat, int turn) {
            std::vector<std::tuple<int, int, int>> prevStates;
            int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
            if (prevTurn == CAT_TURN) {
                for (int prevCat : graph[cat]) {
                    if (prevCat != HOLE) {
                        prevStates.emplace_back(mouse, prevCat, prevTurn);
                    }
                }
            } else {
                for (int prevMouse : graph[mouse]) {
                    prevStates.emplace_back(prevMouse, cat, prevTurn);
                }
            }
            return prevStates;
        };

        std::vector<std::vector<std::vector<int>>> dp(n, std::vector<std::vector<int>>(n, std::vector<int>(2)));
        std::queue<std::tuple<int, int, int>> q;  // (mouse's position, cat's position, whose turn)
        for (int i = 1; i < n; ++i) {
            dp[0][i][MOUSE_TURN] = MOUSE_WIN;
            dp[0][i][CAT_TURN] = MOUSE_WIN;
            dp[i][i][MOUSE_TURN] = CAT_WIN;
            dp[i][i][CAT_TURN] = CAT_WIN;
            q.emplace(0, i, MOUSE_TURN);
            q.emplace(0, i, CAT_TURN);
            q.emplace(i, i, MOUSE_TURN);
            q.emplace(i, i, CAT_TURN);
        }
  
        while (!q.empty()) {
            auto [mouse, cat, turn] = q.front();
            q.pop();

            int res = dp[mouse][cat][turn];
            auto prevStates = getPrevStates(mouse, cat, turn);
            for (auto [prevMouse, prevCat, prevTurn] : prevStates) {
                if (dp[prevMouse][prevCat][prevTurn] == UNKNOWN) {
                    bool winState = (res == MOUSE_WIN && prevTurn == MOUSE_TURN) || (res == CAT_WIN && prevTurn == CAT_TURN);
                    if (winState || --degree[prevMouse][prevCat][prevTurn] == 0) {
                        dp[prevMouse][prevCat][prevTurn] = res;
                        q.emplace(prevMouse, prevCat, prevTurn);
                    }
                }
            }
        }

        return dp[MOUSE_START][CAT_START][MOUSE_TURN];
    }
};
109925