<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 memo[1010][8][8][8][8];
    vector<string>v;
    int cj,mj;
    int R,C;
    int di[4] = {-1,1,0,0};
    int dj[4] = {0,0,1,-1};
    
    bool dp(int nturn, int cx, int cy, int mx, int my) {
        if (nturn %2 == 1) {
            //mouse turn
            if (mx == cx && my == cy) return false; 
            if (nturn > 1000) return false;
            if (v[mx][my] == 'F') return true;
            if (v[cx][cy] == 'F') return false;
        } else {
            //cat turn
            if (mx == cx && my == cy) return true;
            if (nturn > 1000) return true;
            if (v[mx][my] == 'F') return false; 
            if (v[cx][cy] == 'F') return true;
        }
        
        if (memo[nturn][cx][cy][mx][my] != -1) return memo[nturn][cx][cy][mx][my] ;
        bool win = false;
        
        if (nturn %2 == 1) {
            //mouse turn
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j <= mj; j++) {
                    int Mx = mx + j*di[i];
                    int My = my + j*dj[i];
                    if (Mx >= 0 && Mx <R && My>=0 && My <C && v[Mx][My]!= '#') {
                        if (dp(nturn +1, cx,cy,Mx,My) == 0 ) {
                            win = true;
                            break;
                        }
                    }else break;
                }
                if (win)break;
            }
        } else {
            //cat turn
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j <= cj; j++) {
                    int Cx = cx + j*di[i];
                    int Cy = cy + j*dj[i];
                    if (Cx >= 0 && Cx <R && Cy>=0 && Cy <C && v[Cx][Cy]!= '#') {
                        if (dp(nturn +1, Cx,Cy,mx,my) == 0 ) { 
                            win = true;
                            break;
                        }
                    }else break;
                }
                if (win)break;
            }
        }
        
        memo[nturn][cx][cy][mx][my] = win;
        return win;
    }
    
    bool canMouseWin(vector<string>& _v, int _cj, int _mj) {
        memset(memo, -1, sizeof(memo));
        v= _v; cj = _cj; mj = _mj;
        int cx, cy, mx, my;
        R = v.size();
        C = v[0].size();
        
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++) {
                if (v[i][j] == 'C') {
                    cx = i;
                    cy = j;
                }
                
                if (v[i][j] == 'M') {
                    mx = i;
                    my = j;
                }
            }
        return dp(1,cx,cy,mx,my);
    }
};
30300