<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 {
    int n, m, catJump, mouseJump;
    vector<string> grid;
    int dp[65][65][1001];  // Adding the dimension for turns
    int drs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};  
public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        this->grid = grid;
        this->n = grid.size();
        this->m = grid[0].size();
        this->catJump = catJump;
        this->mouseJump = mouseJump;
        memset(dp, -1, sizeof(dp));

        int pos_mouse = 0, pos_cat = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(grid[i][j] == 'C') pos_cat = i * m + j;
                else if(grid[i][j] == 'M') pos_mouse = i * m + j; 
            }
        }

        return DP(pos_mouse, pos_cat, 0);
    }

    bool DP(int mousePos, int catPos, int turn) {
        int r_m = mousePos / m, c_m = mousePos % m;
        int r_c = catPos / m, c_c = catPos % m;

        if(dp[mousePos][catPos][turn] != -1) return dp[mousePos][catPos][turn];
        
        if(turn >= 1000) return dp[mousePos][catPos][turn] = false;  // Too many turns, cat wins
        if(mousePos == catPos) return dp[mousePos][catPos][turn] = false;  // Cat catches mouse
        if(grid[r_m][c_m] == 'F') return dp[mousePos][catPos][turn] = true;  // Mouse reaches food
        if(grid[r_c][c_c] == 'F') return dp[mousePos][catPos][turn] = false;  // Cat reaches food

        bool isMouseTurn = (turn % 2 == 0);
        int maxJump = isMouseTurn ? mouseJump : catJump;

        // Mouse's turn
        if(isMouseTurn) {
            for(int d = 0; d < 4; ++d) {
                for(int l = 0; l <= maxJump; ++l) {  // Mouse can jump <= maxJump
                    int nxtR = r_m + drs[d][0] * l;
                    int nxtC = c_m + drs[d][1] * l;

                    if(nxtR < 0 || nxtR >= n || nxtC < 0 || nxtC >= m || grid[nxtR][nxtC] == '#') break;

                    int nxtPos = nxtR * m + nxtC;
                    if(DP(nxtPos, catPos, turn + 1)) 
                        return dp[mousePos][catPos][turn] = true;
                }
            }

            return dp[mousePos][catPos][turn] = false;
        } else {
            // Cat's turn
            for(int d = 0; d < 4; ++d) {
                for(int l = 0; l <= maxJump; ++l) {  // Cat can jump <= maxJump
                    int nxtR = r_c + drs[d][0] * l;
                    int nxtC = c_c + drs[d][1] * l;

                    if(nxtR < 0 || nxtR >= n || nxtC < 0 || nxtC >= m || grid[nxtR][nxtC] == '#') break;

                    int nxtPos = nxtR * m + nxtC;
                    if(!DP(mousePos, nxtPos, turn + 1))
                        return dp[mousePos][catPos][turn] = false;
                }
            }
            // Cat cannot find a move that forces a win
            return dp[mousePos][catPos][turn] = true;
        }
    }
};

30600