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

// https://github.com/wisdompeak/LeetCode/blob/master/BFS/1728.Cat-and-Mouse-II/1728.Cat-and-Mouse-II.cpp
class Solution {
    static constexpr int MOUSE_TURN = 0, CAT_TURN = 1;
    static constexpr int UNKNOWN = 0, MOUSE_WIN = 1, CAT_WIN = 2;
    static constexpr int MAX_MOVES = 1000;
    static constexpr char WALL = '#';
    static constexpr char CAT = 'C', MOUSE = 'M', FOOD = 'F';

    inline static const std::vector<std::vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        const int rows = grid.size();
        const int cols = grid[0].size();

        int mouseRowStart = -1, mouseColStart = -1;
        int catRowStart = -1, catColStart = -1;
        int foodRow = -1, foodCol = -1;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == MOUSE) {
                    mouseRowStart = i;
                    mouseColStart = j;
                } else if (grid[i][j] == CAT) {
                    catRowStart = i;
                    catColStart = j;
                } else if (grid[i][j] == FOOD) {
                    foodRow = i;
                    foodCol = j;
                }
            }
        }


        std::vector<std::vector<std::vector<std::vector<std::vector<int>>>>> dp(
            rows, std::vector<std::vector<std::vector<std::vector<int>>>>(
                cols, std::vector<std::vector<std::vector<int>>>(
                    rows, std::vector<std::vector<int>>(
                        cols, std::vector<int>(2))))
        );

        std::queue<std::tuple<int, int, int, int, int>> q;
        // 猫和老鼠在同一个单元格，猫获胜
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == WALL) {
                    continue;
                }
                dp[i][j][i][j][MOUSE_TURN] = CAT_WIN;
                dp[i][j][i][j][CAT_TURN] = CAT_WIN;
                q.emplace(i, j, i, j, MOUSE_TURN);
                q.emplace(i, j, i, j, CAT_TURN);
            }
        }
        // 猫和食物在同一个单元格，猫获胜
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == WALL || (i == foodRow && j == foodCol)) {
                    continue;
                }
                dp[i][j][foodRow][foodCol][MOUSE_TURN] = CAT_WIN;
                dp[i][j][foodRow][foodCol][CAT_TURN] = CAT_WIN;
                q.emplace(i, j, foodRow, foodCol, MOUSE_TURN);
                q.emplace(i, j, foodRow, foodCol, CAT_TURN);
            }
        }
        // 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == WALL || (i == foodRow && j == foodCol)) {
                    continue;
                }
                dp[foodRow][foodCol][i][j][MOUSE_TURN] = MOUSE_WIN;
                dp[foodRow][foodCol][i][j][CAT_TURN] = MOUSE_WIN;
                q.emplace(foodRow, foodCol, i, j, MOUSE_TURN);
                q.emplace(foodRow, foodCol, i, j, CAT_TURN);
            }
        }

        auto getPrevStates = [&grid, rows, cols, catJump, mouseJump](int mouseRow, int mouseCol, int catRow, int catCol, int turn) -> std::vector<std::tuple<int, int, int, int, int>> {
            std::vector<std::tuple<int, int, int, int, int>> prevStates;
            int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
            int maxJump = prevTurn == MOUSE_TURN ? mouseJump : catJump;
            int startRow = prevTurn == MOUSE_TURN ? mouseRow : catRow;
            int startCol = prevTurn == MOUSE_TURN ? mouseCol : catCol;
            prevStates.emplace_back(mouseRow, mouseCol, catRow, catCol, prevTurn);
            for (const auto& dir : dirs) {
                for (int i = startRow + dir[0], j = startCol + dir[1], jump = 1; i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] != WALL && jump <= maxJump; i += dir[0], j += dir[1], ++jump) {
                    int prevMouseRow = prevTurn == MOUSE_TURN ? i : mouseRow;
                    int prevMouseCol = prevTurn == MOUSE_TURN ? j : mouseCol;
                    int prevCatRow = prevTurn == MOUSE_TURN ? catRow : i;
                    int prevCatCol = prevTurn == MOUSE_TURN ? catCol : j;
                    prevStates.emplace_back(prevMouseRow, prevMouseCol, prevCatRow, prevCatCol, prevTurn);
                }
            }
            return prevStates;
        };

        auto allNextStateLose = [&dp, &grid, rows, cols, catJump, mouseJump](int mouseRow, int mouseCol, int catRow, int catCol, int turn){
            int startRow = turn == MOUSE_TURN ? mouseRow : catRow;
            int startCol = turn == MOUSE_TURN ? mouseCol : catCol;
            int maxJump = turn == MOUSE_TURN ? mouseJump : catJump;
            int nextTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
            int nextResult = turn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
            if (dp[mouseRow][mouseCol][catRow][catCol][nextTurn] != nextResult) {
                return false;
            }
            for (const auto& dir : dirs) {
                for (int i = startRow + dir[0], j = startCol + dir[1], jump = 1; i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] != WALL && jump <= maxJump; i += dir[0], j += dir[1], ++jump) {
                    int nextMouseRow = turn == MOUSE_TURN ? i : mouseRow;
                    int nextMouseCol = turn == MOUSE_TURN ? j : mouseCol;
                    int nextCatRow = turn == MOUSE_TURN ? catRow : i;
                    int nextCatCol = turn == MOUSE_TURN ? catCol : j;
                    if (dp[nextMouseRow][nextMouseCol][nextCatRow][nextCatCol][nextTurn] != nextResult) {
                        return false;
                    }
                }
            }
            return true;
        };

        // BFS 反推
        int step = 0;
        while (!q.empty()) {
            if (++step > 2 * MAX_MOVES) {
                return false;
            }

            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                auto [mouseRow, mouseCol, catRow, catCol, turn] = q.front();
                q.pop();
                int result = dp[mouseRow][mouseCol][catRow][catCol][turn];
                auto prevStates = getPrevStates(mouseRow, mouseCol, catRow, catCol, turn);
                for (auto& [prevMouseRow, prevMouseCol, prevCatRow, prevCatCol, prevTurn] : prevStates) {
                    if (dp[prevMouseRow][prevMouseCol][prevCatRow][prevCatCol][prevTurn] == UNKNOWN) {
                        bool winState = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
                        if (winState || allNextStateLose(prevMouseRow, prevMouseCol, prevCatRow, prevCatCol, prevTurn)) {
                            dp[prevMouseRow][prevMouseCol][prevCatRow][prevCatCol][prevTurn] = result;
                            q.emplace(prevMouseRow, prevMouseCol, prevCatRow, prevCatCol, prevTurn);
                        }
                    }
                }
            }
        }

        return dp[mouseRowStart][mouseColStart][catRowStart][catColStart][MOUSE_TURN] == MOUSE_WIN;
    }
};
97900