<p>A game is played by a cat and a mouse named Cat and Mouse.</p>

<p>The environment is represented by a <code>grid</code> of size <code>rows x cols</code>, where each element is a wall, floor, player (Cat, Mouse), or food.</p>

<ul>
	<li>Players are represented by the characters <code>&#39;C&#39;</code>(Cat)<code>,&#39;M&#39;</code>(Mouse).</li>
	<li>Floors are represented by the character <code>&#39;.&#39;</code> and can be walked on.</li>
	<li>Walls are represented by the character <code>&#39;#&#39;</code> and cannot be walked on.</li>
	<li>Food is represented by the character <code>&#39;F&#39;</code> and can be walked on.</li>
	<li>There is only one of each character <code>&#39;C&#39;</code>, <code>&#39;M&#39;</code>, and <code>&#39;F&#39;</code> in <code>grid</code>.</li>
</ul>

<p>Mouse and Cat play according to the following rules:</p>

<ul>
	<li>Mouse <strong>moves first</strong>, then they take turns to move.</li>
	<li>During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the <code>grid</code>.</li>
	<li><code>catJump, mouseJump</code> are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.</li>
	<li>Staying in the same position is allowed.</li>
	<li>Mouse can jump over Cat.</li>
</ul>

<p>The game can end in 4 ways:</p>

<ul>
	<li>If Cat occupies the same position as Mouse, Cat wins.</li>
	<li>If Cat reaches the food first, Cat wins.</li>
	<li>If Mouse reaches the food first, Mouse wins.</li>
	<li>If Mouse cannot get to the food within 1000 turns, Cat wins.</li>
</ul>

<p>Given a <code>rows x cols</code> matrix <code>grid</code> and two integers <code>catJump</code> and <code>mouseJump</code>, return <code>true</code><em> if Mouse can win the game if both Cat and Mouse play optimally, otherwise return </em><code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/12/sample_111_1955.png" style="width: 580px; height: 239px;" />
<pre>
<strong>Input:</strong> grid = [&quot;####F&quot;,&quot;#C...&quot;,&quot;M....&quot;], catJump = 1, mouseJump = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> Cat cannot catch Mouse on its turn nor can it get the food before Mouse.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/12/sample_2_1955.png" style="width: 580px; height: 175px;" />
<pre>
<strong>Input:</strong> grid = [&quot;M.C...F&quot;], catJump = 1, mouseJump = 4
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [&quot;M.C...F&quot;], catJump = 1, mouseJump = 3
<strong>Output:</strong> false
</pre>

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

<ul>
	<li><code>rows == grid.length</code></li>
	<li><code>cols = grid[i].length</code></li>
	<li><code>1 &lt;= rows, cols &lt;= 8</code></li>
	<li><code>grid[i][j]</code> consist only of characters <code>&#39;C&#39;</code>, <code>&#39;M&#39;</code>, <code>&#39;F&#39;</code>, <code>&#39;.&#39;</code>, and <code>&#39;#&#39;</code>.</li>
	<li>There is only one of each character <code>&#39;C&#39;</code>, <code>&#39;M&#39;</code>, and <code>&#39;F&#39;</code> in <code>grid</code>.</li>
	<li><code>1 &lt;= catJump, mouseJump &lt;= 8</code></li>
</ul>

using namespace std;

class Solution {
public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        const int MOUSE_TURN = 1, CAT_TURN = 2;  // Define constants for turn tracking
        const int MOUSE_WIN = 1, CAT_WIN = 2, DRAW = 0;  // Game result constants

        int rows = grid.size();  // Get the number of rows in the grid
        int cols = grid[0].size();  // Get the number of columns in the grid

        // Maps for position-to-ID and ID-to-position for easy grid navigation
        unordered_map<int, pair<int, int>> id_position;  // Map position ID to (row, col)
        unordered_map<pair<int, int>, int, pair_hash> position_id;  // Map (row, col) to position ID
        int pos_id = 0;  // Position ID counter
        pair<int, int> mouse_start, cat_start, food_pos;  // Variables to store positions of Mouse, Cat, and Food

        // Identify Mouse, Cat, and Food positions, and map non-wall cells to IDs
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] != '#') {  // Only process non-wall cells
                    pair<int, int> pos = { r, c };  // Current position in the grid
                    position_id[pos] = pos_id;  // Map (row, col) to position ID
                    id_position[pos_id] = pos;  // Map position ID to (row, col)

                    // Identify the starting positions of Mouse, Cat, and Food
                    if (grid[r][c] == 'M') {
                        mouse_start = pos;
                    }
                    else if (grid[r][c] == 'C') {
                        cat_start = pos;
                    }
                    else if (grid[r][c] == 'F') {
                        food_pos = pos;
                    }
                    pos_id++;  // Increment position ID for the next valid position
                }
            }
        }

        int total_positions = pos_id;  // Total number of valid positions

        // Helper function to compute valid moves for a given position within the jump limit
        auto get_moves = [&](int pos_id, int max_jump) -> vector<int> {
            vector<int> moves;  // Vector to store all possible moves
            pair<int, int> pos = id_position[pos_id];  // Get (row, col) of the current position
            int r0 = pos.first, c0 = pos.second;  // Store the current row and column
            vector<pair<int, int>> directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };  // Directions for up, down, left, right

            moves.push_back(pos_id);  // Staying in the same position is always valid

            // For each direction, check if moving within the jump limit is valid
            for (size_t i = 0; i < directions.size(); ++i) {
                int dr = directions[i].first;  // Direction row offset
                int dc = directions[i].second;  // Direction column offset
                for (int jump = 1; jump <= max_jump; ++jump) {
                    int r = r0 + dr * jump;  // New row after the jump
                    int c = c0 + dc * jump;  // New column after the jump
                    // Check if the new position is valid (within bounds and not a wall)
                    if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] != '#') {
                        moves.push_back(position_id[{r, c}]);  // Add valid position
                    }
                    else {
                        break;  // Stop if the move hits a wall or goes out of bounds
                    }
                }
            }
            return moves;  // Return all valid moves
        };

        // Precompute valid moves for all positions for both Mouse and Cat
        vector<vector<int>> mouse_moves(total_positions), cat_moves(total_positions);
        for (int i = 0; i < total_positions; ++i) {
            mouse_moves[i] = get_moves(i, mouseJump);  // Mouse's possible moves
            cat_moves[i] = get_moves(i, catJump);  // Cat's possible moves
        }

        const int MAX_TURNS = 70;  // Maximum turns to avoid infinite loops
        vector<vector<vector<int>>> dp(total_positions, vector<vector<int>>(total_positions, vector<int>(2, DRAW)));  // DP table to track game state
        deque<tuple<int, int, int, int>> queue;  // Queue for BFS processing

        // Initialize terminal states where Mouse or Cat has already won
        for (int mouse_pos = 0; mouse_pos < total_positions; ++mouse_pos) {
            for (int cat_pos = 0; cat_pos < total_positions; ++cat_pos) {
                // Case where Cat catches Mouse, but not at the food
                if (mouse_pos == cat_pos && mouse_pos != position_id[food_pos]) {
                    dp[mouse_pos][cat_pos][0] = CAT_WIN;
                    dp[mouse_pos][cat_pos][1] = CAT_WIN;
                    queue.push_back(make_tuple(mouse_pos, cat_pos, MOUSE_TURN, CAT_WIN));
                    queue.push_back(make_tuple(mouse_pos, cat_pos, CAT_TURN, CAT_WIN));
                }
                // Case where Mouse reaches the food
                if (mouse_pos == position_id[food_pos]) {
                    dp[mouse_pos][cat_pos][0] = MOUSE_WIN;
                    dp[mouse_pos][cat_pos][1] = MOUSE_WIN;
                    queue.push_back(make_tuple(mouse_pos, cat_pos, MOUSE_TURN, MOUSE_WIN));
                    queue.push_back(make_tuple(mouse_pos, cat_pos, CAT_TURN, MOUSE_WIN));
                }
                // Case where Cat reaches the food
                if (cat_pos == position_id[food_pos]) {
                    dp[mouse_pos][cat_pos][0] = CAT_WIN;
                    dp[mouse_pos][cat_pos][1] = CAT_WIN;
                    queue.push_back(make_tuple(mouse_pos, cat_pos, MOUSE_TURN, CAT_WIN));
                    queue.push_back(make_tuple(mouse_pos, cat_pos, CAT_TURN, CAT_WIN));
                }
            }
        }

        // Array to keep track of remaining valid moves (degrees of freedom) for each state
        vector<vector<vector<int>>> degrees(total_positions, vector<vector<int>>(total_positions, vector<int>(2, 0)));
        for (int mouse_pos = 0; mouse_pos < total_positions; ++mouse_pos) {
            for (int cat_pos = 0; cat_pos < total_positions; ++cat_pos) {
                degrees[mouse_pos][cat_pos][0] = mouse_moves[mouse_pos].size();  // Mouse's available moves
                degrees[mouse_pos][cat_pos][1] = cat_moves[cat_pos].size();  // Cat's available moves
            }
        }

        // BFS to propagate game state information from terminal states to other states
        while (!queue.empty()) {
            tuple<int, int, int, int> state = queue.front();
            queue.pop_front();
            int mouse_pos = get<0>(state);  // Mouse's position
            int cat_pos = get<1>(state);  // Cat's position
            int turn = get<2>(state);  // Current turn (mouse or cat)
            int result = get<3>(state);  // Result of the current state (mouse win, cat win, draw)

            // Get the previous turn (switch between mouse and cat)
            int prev_turn = (turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN);
            vector<int>& prev_moves = (prev_turn == MOUSE_TURN) ? mouse_moves[mouse_pos] : cat_moves[cat_pos];  // Get the previous player's valid moves

            // Process each previous move to update game state
            for (size_t i = 0; i < prev_moves.size(); ++i) {
                int prev_pos = prev_moves[i];
                int prev_mouse_pos = (prev_turn == MOUSE_TURN) ? prev_pos : mouse_pos;
                int prev_cat_pos = (prev_turn == CAT_TURN) ? prev_pos : cat_pos;

                // If the previous state is already determined, skip
                if (dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1] != DRAW) {
                    continue;
                }

                // If the previous player can force a win, update the state and enqueue
                if ((prev_turn == MOUSE_TURN && result == MOUSE_WIN) || (prev_turn == CAT_TURN && result == CAT_WIN)) {
                    dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1] = result;
                    queue.push_back(make_tuple(prev_mouse_pos, prev_cat_pos, prev_turn, result));
                }
                else {
                    // Otherwise, decrease the degree and if no more moves, force a loss
                    degrees[prev_mouse_pos][prev_cat_pos][prev_turn - 1]--;
                    if (degrees[prev_mouse_pos][prev_cat_pos][prev_turn - 1] == 0) {
                        dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1] = (prev_turn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN);
                        queue.push_back(make_tuple(prev_mouse_pos, prev_cat_pos, prev_turn, dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1]));
                    }
                }
            }
        }

        // Check if the mouse can win starting from the initial state
        return dp[position_id[mouse_start]][position_id[cat_start]][0] == MOUSE_WIN;
    }

private:
    // Hash function for pair<int, int> for unordered_map
    struct pair_hash {
        template <class T1, class T2>
        std::size_t operator() (const std::pair<T1, T2>& p) const {
            return std::hash<T1>()(p.first) ^ std::hash<T2>()(p.second);
        }
    };
};

33300