<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:
int dp[64][64][64] = {};
int dirs[5] = {0, 1, 0, -1, 0};
vector<int> getJumps(vector<string>& g, int p, int f, int max) {
    vector<int> res{p};
    for (auto d = 0; d < 4; ++d)
        for (int jump = 1; jump <= max; ++jump) {
            auto i = p / 8 + dirs[d] * jump, j = p % 8 + dirs[d + 1] * jump;
            if (i < 0 || j < 0 || i >= g.size() || j >= g[i].size() || g[i][j] == '#')
                break;
            res.push_back(i * 8 + j);
        }
    sort(begin(res), end(res), [f](int a, int b) { return abs(f / 8 - a / 8) + abs(f % 8 - a % 8) <
            abs(f / 8 - b / 8) + abs(f % 8 - b % 8); });
    return res;
}
bool dfs(vector<string>& g, int turn, int c, int m, int f, int catJump, int mouseJump) {
    if (turn >= 0 && (m == f || dp[turn][m][c] == 1))
        return true;
    if (turn < 0 || c == m || c == f || dp[turn][m][c] == -1)
        return false;
    auto catJumps = getJumps(g, c, f, catJump);
    for (auto new_m : getJumps(g, m, f, mouseJump)) {
        bool mouseWon = true;
        for (auto n = 0; mouseWon && n < catJumps.size(); ++n)
            mouseWon &= dfs(g, turn - 1, catJumps[n], new_m, f, catJump, mouseJump);
        if (mouseWon)
            return dp[turn][m][c] = 1;
    }
    dp[turn][m][c] = -1;
    return false;
}
bool canMouseWin(vector<string>& g, int catJump, int mouseJump) {
    int c = 0, m = 0, f = 0, rows = g.size(), cols = g[0].size();
    int turns = rows * cols - 1;
    for (auto i = 0; i < rows; ++i)
        for (auto j = 0; j < cols; ++j) {
            m = g[i][j] == 'M' ? i * 8 + j : m;
            c = g[i][j] == 'C' ? i * 8 + j : c;
            f = g[i][j] == 'F' ? i * 8 + j : f;
        }
    return dfs(g, turns, c, m, f, catJump, mouseJump);
}
};
42500