<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[]
// bool Valid(int i,int j,int n,int m,vector<string>&grid){
//     if(i<n && j<m && i>=0 && j>=0 && grid[i][j]!='#')return true;
//     else return false;
// }
// bool DFS(int m1,int m2,int c1,int c2,int f1,int f2,vector<string>&grid,int cat,int mouse,int term,vector<vector<vector<vector<vector<int>>>>>&dp,int n,int m){
// int x[4]={-1,1,0,0};
// int y[4]={0,0,1,-1};
//     if(m1==f1 && m2==f2)return true;
//     if(c1==f1 && c2==f2)return true;
//     if(c1==f1 && c2==f2)return false;
//     if(term>1000)return false;
//     if(dp[m1][m2][c1][c2][term]!=-1)return dp[m1][m2][c1][c2][term];
//     int finalp=0;
//     if(term&1){
//          for(int i=0;i<4;i++){
//             int p=0;
//             for(int j=0;j<=cat && !p;j++){
//                 int row=c1+x[i]*j;
//                 int col=c2+y[i]*j;
//                 if(Valid(row,col,n,m,grid)){
//                     p=p|DFS(m1,m2,row,col,f1,f2,grid,cat,mouse,term+1,dp,n,m);
//                 }
//             }
//             finalp=p;

//          }
//     }else {
//         for(int i=0;i<4;i++){
//             int p=1;
//             for(int j=0;j<=mouse && p;j++){
//                 int row=m1+x[i]*j;
//                 int col=m2+y[i]*j;
//                 if(Valid(row,col,n,m,grid) && !(row==c1 && col==c2) ){
//                     p=p&DFS(row,col,c1,c2,f1,f2,grid,cat,mouse,term+1,dp,n,m);
//                 }
//             }
//             finalp=p&finalp;
//         }

//     }
//     return dp[m1][m2][c1][c2][term]=finalp;
// }
//     bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
//         int n=grid.size();
//         int m=grid[0].size();
//         int i1=0,j1=0,i2=0,j2=0,f1=0,f2=0;
//         for(int i=0;i<grid.size();i++){
//             for(int j=0;j<grid[0].size();j++){
//                 if(grid[i][j]=='F'){
//                     f1=i;
//                     f2=j;
//                 }else if(grid[i][j]=='C'){
//                     i2=i;
//                     j2=j;
//                 }else if(grid[i][j]=='M'){
//                     i1=i;
//                     j1=j;
//                 }
//             }
//         }
        
//         return DFS(i1,j1,i2,j2,f1,f2,grid,catJump,mouseJump,0,dp,n,m);
//     }
// };
class Solution {
public:
    //rows and cols are 8*8 atmax therefore, cat and mouse both can reach anywhere they want in at max ~70 steps even if catJump, mouseJump=1.
    
    //let's indicate win as 1 and loss as 0.
    int n,m;
    
    int dp[1001][9][9][9][9]; //turns, ci, cj, mi, mj
    
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    
    int solve(int turns, int ci, int cj, int mi, int mj, int catJump, int mouseJump, vector<string>& grid){
        int x=turns%2;
        int ans=0;
        if(x==0){ //mouse
            if(turns>=1000)
            return 0;
            if (mi==ci && mj==cj) 
                return 0;//mouse gets caught by cat, it loses
            if (grid[mi][mj] == 'F') 
                return 1;//mouse got the food, it wins
            if (grid[ci][cj] == 'F') 
                return 0; //cat got the food, mouse loses
            if(dp[turns][ci][cj][mi][mj]!=-1)
                return dp[turns][ci][cj][mi][mj];
             for(int i=0;i<4;i++){
                       for(int j=0;j<=mouseJump;j++){
                           int mx=mi+j*dx[i];
                           int my=mj+j*dy[i];
                           if(mx>=0 && my>=0 && mx<n && my<m && grid[mx][my]!='#'){
                               if(solve(turns+1, ci, cj, mx, my, catJump, mouseJump, grid)==0){ //if in the next turn cat loses
                                   ans=1;
                                   break;
                               }
                           }
                           else
                               break;
                     }
                    if(ans)
                        break;
             }
        }
        else{ //cat
            if(turns>=1000)
            return 1;
            if (mi==ci && mj==cj) 
                return 1;//mouse gets caught by cat, cat wins
            if (grid[mi][mj] == 'F') 
                return 0;//mouse got the food, cat loses
            if (grid[ci][cj] == 'F') 
                return 1; //cat got the food, it wins
            if(dp[turns][ci][cj][mi][mj]!=-1)
                return dp[turns][ci][cj][mi][mj];
            for(int i=0;i<4;i++){
                for(int j=0;j<=catJump;j++){
                           int cx=ci+j*dx[i];
                           int cy=cj+j*dy[i];
                           if(cx>=0 && cy>=0 && cx<n && cy<m && grid[cx][cy]!='#'){ 
                               if(solve(turns+1, cx, cy, mi, mj, catJump, mouseJump, grid)==0){ //if in the next turn mouse loses
                                   ans=1;
                                   break;
                               }
                           }
                           else
                               break;
                     }
                    if(ans)
                        break;
             }
        }
        return dp[turns][ci][cj][mi][mj]=ans;
        
    }
    
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        n=grid.size();
        m=grid[0].size();
        int ci,cj,mi,mj;
        memset(dp, -1, sizeof(dp));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='C'){
                    ci=i;
                    cj=j;
                }
                else if(grid[i][j]=='M'){
                    mi=i;
                    mj=j;
                }
            }
        }
        return solve(0, ci, cj, mi, mj, catJump, mouseJump, grid);
    }
};
40800