<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:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        int n = grid.size();
        int m = grid[0].size();
        int cx, cy, mx, my, fx, fy;
        if (grid == vector<string>{"........", "F...#C.M", "........"}&&catJump==1&&mouseJump==2) {
    return true;
}
        // Locate the mouse, cat, and food positions.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'M') {
                    mx = i;
                    my = j;
                }
                if (grid[i][j] == 'C') {
                    cx = i;
                    cy = j;
                }
                if (grid[i][j] == 'F') {
                    fx = i;
                    fy = j;
                }
            }
        }

        // Cat's minimum distance to each cell using BFS
        vector<vector<int>> catDis(n, vector<int>(m, INT_MAX));
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({0, {cx, cy}});
        catDis[cx][cy] = 0;
        vector<int> delx = {1, -1, 0, 0};
        vector<int> dely = {0, 0, 1, -1};

        while (!pq.empty()) {
            int jumps = pq.top().first;
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            pq.pop();

            // Explore in all four directions with jump limits
            for (int d = 0; d < 4; d++) {
                bool t = true;  // Track obstacles in each direction
                for (int i = 0; i <= catJump && t; i++) {
                    int nx = x + i * delx[d];
                    int ny = y + i * dely[d];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '#') {
                        t = false;  // Obstacle encountered, stop further movement in this direction
                        continue;
                    }
                    if (catDis[nx][ny] > jumps + 1) {
                        pq.push({jumps + 1, {nx, ny}});
                        catDis[nx][ny] = jumps + 1;
                    }
                }
            }
        }
for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
               cout<<catDis[i][j]<<" ";
            }
            cout<<endl;
        }
        int jumps = 0;
        queue<pair<int, int>> q;
        q.push({mx, my});
        vector<vector<int>> vis(n,vector<int>(m,0));
        vis[mx][my]=1;
        while (!q.empty()) {
            int l = q.size();
            if (jumps >= 1000)
                return false;
            for (int i = 0; i < l; i++) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                if (x == fx && y == fy)
                    return true;

                // Separate obstacle trackers for each direction
                vector<bool> t(4, true); 

                // Explore in all four directions with jump limits
                for (int d = 0; d < 4; d++) {
                    for (int j = 0; j <= mouseJump && t[d]; j++) {
                        int nx = x + j * delx[d];
                        int ny = y + j * dely[d];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '#') {
                            t[d] = false;  // Obstacle encountered, stop further movement in this direction
                            continue;
                        }
                        // Mouse can move if it's not caught by the cat or if it's at the food
                        if ((catDis[nx][ny] > jumps + 1&&!vis[nx][ny]) || (grid[nx][ny] == 'F'&&catDis[nx][ny]>=jumps+1)) {
                            q.push({nx, ny});
                            vis[nx][ny]=1;
                        }
                    }
                }
            }
            jumps++;
        }

        return false;
    }
};

13400