<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[10][10][10][10][1010];

    bool rec_func(int x1, int y1, int x2, int y2,int n, int catjump, int mousejump,vector<string>& grid){
        //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<n<<endl;
        int &v=dp[x1][y1][x2][y2][n];
        if(v!=-1) return v;
        if(n==70){
            return v=0;
        }
        if(x1==x2 && y1==y2) return v=0;
        int x_r,y_r,x_c,y_c;
        for(int dir1=0;dir1<4;dir1++){
            //for(int dir2=0;dir2<4;dir2++){
                for(int i=0;i<=mousejump;i++){
                    if(dir1==0){
                        x_r=x1+i;
                        y_r=y1;
                    }
                    else if(dir1==1){
                        x_r=x1;
                        y_r=y1+i;
                    }
                    else if(dir1==2){
                        x_r=x1-i;
                        y_r=y1;
                    }
                    else{
                        x_r=x1;
                        y_r=y1-i;
                    }
                    if(x_r>=grid.size() |x_r<0|y_r<0| y_r>=grid[0].length()) break;
                    if(grid[x_r][y_r]=='#') break;
                    if(grid[x_r][y_r]=='F') return v=1;



                    int flag=0;
                    int flag2=0;
                    for(int dir2=0;dir2<4;dir2++){
                    for(int j=0;j<=catjump;j++){
                        if(dir2==0){
                            x_c=x2+j;
                            y_c=y2;
                        }
                        else if(dir2==1){
                            x_c=x2;
                            y_c=y2+j;
                        }
                        else if(dir2==2){
                            x_c=x2-j;
                            y_c=y2;
                        }
                        else{
                            x_c=x2;
                            y_c=y2-j;
                        }
                        if(x_c>=grid.size() |x_c<0|y_c<0| y_c>=grid[0].length()) break;
                        if(grid[x_c][y_c]=='#') break;
                        if(grid[x_c][y_c]=='F') {flag=1;break;}
                        if(rec_func(x_r,y_r,x_c,y_c,n+1,catjump,mousejump,grid)==1) flag2=1;

                        else {flag=1;break;}



                    }
                    }
                    if(flag==0 && flag2==1) return v=1;
                }
            //}
        }

        return v=0;


    }


    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        memset(dp,-1,sizeof(dp));
        int n=grid.size();
        int m=grid[0].length();
        int x_r,y_r,x_c,y_c;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='C'){
                    x_c=i;
                    y_c=j;
                }
                if(grid[i][j]=='M'){
                    x_r=i;
                    y_r=j;
                }
            }
        }
        return rec_func(x_r,y_r,x_c,y_c,0,catJump,mouseJump,grid);
    }
};
56200