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

class Solution {
public:    
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        int rows = grid.size(), cols = grid[0].size();
        int catStartPos = findPos(rows, cols, grid, 'C');
        int mouseStartPos = findPos(rows, cols, grid, 'M');
        int foodPos = findPos(rows, cols, grid, 'F');
        vector<vector<int>> catTransitions = getTransitions(rows, cols, grid, catJump);
        vector<vector<int>> mouseTransitions = getTransitions(rows, cols, grid, mouseJump);

        // states[catPos][mousePos][isMouseMove]
        // = 0 for undetermined outcome, 1 for cat will win, 2 for mouse will win
        vector<vector<array<int, 2>>> states(rows * cols, vector<array<int, 2>>(rows * cols));
        // catPos, mousePos, isMouseMove
        queue<array<int, 3>> endStates;
        // number of next states that result in a loss
        vector<vector<array<int, 2>>> loseCounter(rows * cols, vector<array<int, 2>>(rows * cols));

        for (int i = 0; i < rows * cols; i++) {
            if (i == foodPos || grid[i / cols][i % cols] == '#') {
                continue;
            }
            states[foodPos][i] = {1, 1}; // cat at food
            states[i][foodPos] = {2, 2}; // mouse at food
            states[i][i] = {1, 1}; // cat caught mouse
            endStates.push({foodPos, i, false});
            endStates.push({foodPos, i, true});
            endStates.push({i, foodPos, false});
            endStates.push({i, foodPos, true});
            endStates.push({i, i, false});
            endStates.push({i, i, true});
        }
        
        // bfs from all end states
        while (endStates.size() > 0 && states[catStartPos][mouseStartPos][1] == 0) {
            auto [catPos, mousePos, isMouseMove] = endStates.front();
            endStates.pop();
            if (states[catPos][mousePos][isMouseMove] == isMouseMove + 1) {
                // end state is where cat/mouse can win on their turn
                // any previous state for mouse/cat that only leads to a win for cat/mouse must be a losing state
                if (isMouseMove) {
                    for (int previousCatPos : catTransitions[catPos]) {
                        if (states[previousCatPos][mousePos][!isMouseMove] == 0 && (++loseCounter[previousCatPos][mousePos][!isMouseMove]) == catTransitions[previousCatPos].size()) {
                            states[previousCatPos][mousePos][!isMouseMove] = 2;
                            endStates.push({previousCatPos, mousePos, !isMouseMove});
                        }
                    }
                } else {
                    for (int previousMousePos : mouseTransitions[mousePos]) {
                        if (states[catPos][previousMousePos][!isMouseMove] == 0 && (++loseCounter[catPos][previousMousePos][!isMouseMove]) == mouseTransitions[previousMousePos].size()) {
                            states[catPos][previousMousePos][!isMouseMove] = 1;
                            endStates.push({catPos, previousMousePos, !isMouseMove});
                        }
                    }
                }
            } else if (states[catPos][mousePos][isMouseMove] == 2 - isMouseMove) {
                // end state is where cat/mouse must lose on their turn
                // any previous state for mouse/cat that can lead to a loss for cat/mouse must be a winning state
                if (isMouseMove) {
                    for (int previousCatPos : catTransitions[catPos]) {
                        if (states[previousCatPos][mousePos][!isMouseMove] == 0) {
                            states[previousCatPos][mousePos][!isMouseMove] = 1;
                            endStates.push({previousCatPos, mousePos, !isMouseMove});
                        }
                    }
                } else {
                    for (int previousMousePos : mouseTransitions[mousePos]) {
                        if (states[catPos][previousMousePos][!isMouseMove] == 0) {
                            states[catPos][previousMousePos][!isMouseMove] = 2;
                            endStates.push({catPos, previousMousePos, !isMouseMove});
                        }
                    }
                }
            }
        }
        return states[catStartPos][mouseStartPos][1] == 2;
    }

private:
    int findPos(int rows, int cols, vector<string>& grid, char c) {
        for (int i = 0; i < rows * cols; i++) {
            if (grid[i / cols][i % cols] == c) {
                return i;
            }
        }
        return -1;
    }

    vector<vector<int>> getTransitions(int rows, int cols, vector<string>& grid, int jump) {
        vector<vector<int>> transitions(rows * cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '#') {
                    continue;
                }
                transitions[i * cols + j].push_back(i * cols + j);
                for (int k = i - 1; k >= max(i - jump, 0) && grid[k][j] != '#'; k--) {
                    transitions[i * cols + j].push_back(k * cols + j);
                }
                for (int k = i + 1; k <= min(i + jump, rows - 1) && grid[k][j] != '#'; k++) {
                    transitions[i * cols + j].push_back(k * cols + j);
                }
                for (int k = j - 1; k >= max(j - jump, 0) && grid[i][k] != '#'; k--) {
                    transitions[i * cols + j].push_back(i * cols + k);
                }
                for (int k = j + 1; k <= min(j + jump, cols - 1) && grid[i][k] != '#'; k++) {
                    transitions[i * cols + j].push_back(i * cols + k);
                }
            }
        }
        return transitions;
    }
};
19800