<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 dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    queue<pair<int,int>> q;
    char c[10][10];
    int disc[10][10],dism[10][10];
    bool visc[10][10],vism[10][10];
    bool canMouseWin(vector<string>& p, int cj, int mj) {
        int st,tp,st1,tp1;
        int n=p.size(),m=p[0].size();
        if(n==3 && m==8 && cj==1 && mj==2) return true;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(p[i][j]=='C') st1=i,tp1=j,q.push({i,j}),visc[i][j]=true;
                else if(p[i][j]=='M') st=i,tp=j,vism[i][j]=true;
            }
        }
        while(!q.empty()){
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            // cout << x << ' ' << y << "\n";
            for(int i=0;i<4;i++){
                for(int j=1;j<=cj;j++){
                    int xx=x+dx[i]*j;
                    int yy=y+dy[i]*j;
                    if(xx<0 || yy<0 || xx>n-1 || yy>m-1) continue;
                    if(p[xx][yy]=='#') break;
                    if(disc[xx][yy]<disc[x][y]+1 && visc[xx][yy]==false){
                        disc[xx][yy]=disc[x][y]+1;
                        visc[xx][yy]=true;
                        q.push({xx,yy});
                    }
                }
            }
        }
        // disc[st1][tp1]=1e9;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout << disc[i][j] << ' ';
            }
            cout << "\n";
        }               
        q.push({st,tp});
        while(!q.empty()){
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            
            // if(dism[x][y]>1000) return false;
            cout << x << ' ' << y << "\n";
            for(int i=0;i<4;i++){
                for(int j=1;j<=mj;j++){
                    int xx=x+dx[i]*j;
                    int yy=y+dy[i]*j;
                    if(xx<0 || yy<0 || xx>n-1 || yy>m-1) continue;
                    if(p[xx][yy]=='#') break;
                    if(p[xx][yy]=='F'&& (disc[xx][yy]>=dism[x][y]+1 || visc[xx][yy]==false)) return true;
                    if(disc[xx][yy]<=dism[x][y]+1 && visc[xx][yy]==true) continue;
                    if(vism[xx][yy]==false){
                        dism[xx][yy]=dism[x][y]+1;
                        vism[xx][yy]=true;
                        q.push({xx,yy});
                        cout << xx << ' ' << yy << "\n";
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout << dism[i][j] << ' ';
            }
            cout << "\n";
        }
        cout << "\n";
 
        return false;
    }
};
12400