<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;
    int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};
     int dp[140][8][8][8][8];
    vector<int> cat,food,mouse;
    int solve(int c0,int c1,int m0,int m1,vector<string>& grid, int cj, int mj,int turn)
    {
        if(turn>=128)
        {
            return 0;
        }
        if (dp[turn][m0][m1][c0][c1] != -1) return dp[turn][m0][m1][c0][c1];
        int ret=turn%2==0?0:1;
        if(turn%2==0)//mouse
        {
            if(c0==m0 && c1==m1)
            {
                ret=0;
            }
            else if(m0==food[0] && m1==food[1])
            {
                ret=1;
            }
             else if(c0==food[0] && c1==food[1])
            {
                ret=0;
            }
            else
            {
                for(int i=0;i<4;i++)
                {
                    for(int j=0;j<=mj;j++)
                    {
                        int x=m0+j*dx[i];
                        int y=m1+j*dy[i];
                        
                        if(x>=0 && y>=0 && y<m && x<n && grid[x][y]!='#')
                        {
                            if(solve(c0,c1,x,y,grid,cj,mj,turn+1))
                            {
                                ret=1;
                                break;
                            }
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                
            }
            
        }
        else
        {
             if(c0==m0 && c1==m1)
            {
                ret=0;
            }
            else if(c0==food[0] && c1==food[1])
            {
                ret=0;
            }
               else if(m0==food[0] && m1==food[1])
            {
                ret=1;
            }
            else
            {
                for(int i=0;i<4;i++)
                {
                    for(int j=0;j<=cj;j++)
                    {
                        int x=c0+j*dx[i];
                        int y=c1+j*dy[i];
                        
                        if(x>=0 && y>=0 && y<m && x<n && grid[x][y]!='#')
                        {
                            if(solve(x,y,m0,m1,grid,cj,mj,turn+1)==0)
                            {
                                ret=0;
                                break;
                            }
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                
            }
            
        }
        return dp[turn][m0][m1][c0][c1]=ret;
    }
public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
         memset(dp, -1, sizeof(dp));
          cat.resize(2); mouse.resize(2); food.resize(2);
        int R = grid.size();int C = grid[0].size();
        n=R;m=C;
          for (int i=0; i<R; i++) {
           for (int j=0; j<C; j++) {
                if (grid[i][j] == 'C') cat[0] = i, cat[1] = j;
                else if (grid[i][j] == 'M') mouse[0] = i, mouse[1] = j;
                else if (grid[i][j] == 'F') food[0] = i, food[1] = j;
            }
        }
        return solve(cat[0],cat[1],mouse[0],mouse[1],grid,catJump,mouseJump,0);
    }
};
14300