<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:
    def canMouseWin(self, grid, catJump, mouseJump):
        from collections import deque
        MOUSE_TURN, CAT_TURN = 1, 2
        MOUSE_WIN, CAT_WIN, DRAW = 1, 2, 0

        rows, cols = len(grid), len(grid[0])

        # Map positions to indices
        position_id = {}
        id_position = {}
        pos_id = 0
        walls = set()
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != '#':
                    pos = (r, c)
                    position_id[pos] = pos_id
                    id_position[pos_id] = pos
                    if grid[r][c] == 'M':
                        mouse_start = pos_id
                    elif grid[r][c] == 'C':
                        cat_start = pos_id
                    elif grid[r][c] == 'F':
                        food_pos = pos_id
                    pos_id += 1
                else:
                    walls.add((r, c))

        total_positions = pos_id

        # Precompute possible moves
        def get_moves(pos_id, max_jump):
            moves = []
            r0, c0 = id_position[pos_id]
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            moves.append(pos_id)  # Staying in the same position
            for dr, dc in directions:
                for jump in range(1, max_jump + 1):
                    r, c = r0 + dr * jump, c0 + dc * jump
                    if 0 <= r < rows and 0 <= c < cols and grid[r][c] != '#':
                        moves.append(position_id[(r, c)])
                    else:
                        break
            return moves

        mouse_moves = [get_moves(pos_id, mouseJump) for pos_id in range(total_positions)]
        cat_moves = [get_moves(pos_id, catJump) for pos_id in range(total_positions)]

        MAX_TURNS = 70  # Based on the problem constraints
        dp = [[[DRAW] * 2 for _ in range(total_positions)] for _ in range(total_positions)]
        queue = deque()

        # Initialize terminal states
        for mouse_pos in range(total_positions):
            for cat_pos in range(total_positions):
                if mouse_pos == cat_pos and mouse_pos != food_pos:
                    dp[mouse_pos][cat_pos][0] = CAT_WIN
                    dp[mouse_pos][cat_pos][1] = CAT_WIN
                    queue.append((mouse_pos, cat_pos, MOUSE_TURN, CAT_WIN))
                    queue.append((mouse_pos, cat_pos, CAT_TURN, CAT_WIN))
                if mouse_pos == food_pos:
                    dp[mouse_pos][cat_pos][0] = MOUSE_WIN
                    dp[mouse_pos][cat_pos][1] = MOUSE_WIN
                    queue.append((mouse_pos, cat_pos, MOUSE_TURN, MOUSE_WIN))
                    queue.append((mouse_pos, cat_pos, CAT_TURN, MOUSE_WIN))
                if cat_pos == food_pos:
                    dp[mouse_pos][cat_pos][0] = CAT_WIN
                    dp[mouse_pos][cat_pos][1] = CAT_WIN
                    queue.append((mouse_pos, cat_pos, MOUSE_TURN, CAT_WIN))
                    queue.append((mouse_pos, cat_pos, CAT_TURN, CAT_WIN))

        # Degrees of freedom for each state
        degrees = [[[0] * 2 for _ in range(total_positions)] for _ in range(total_positions)]
        for mouse_pos in range(total_positions):
            for cat_pos in range(total_positions):
                degrees[mouse_pos][cat_pos][0] = len(mouse_moves[mouse_pos])
                degrees[mouse_pos][cat_pos][1] = len(cat_moves[cat_pos])

        # BFS to fill dp table
        while queue:
            mouse_pos, cat_pos, turn, result = queue.popleft()
            prev_turn = CAT_TURN if turn == MOUSE_TURN else MOUSE_TURN
            prev_moves = mouse_moves if prev_turn == MOUSE_TURN else cat_moves
            prev_positions = prev_moves[mouse_pos if prev_turn == MOUSE_TURN else cat_pos]

            for prev_pos in prev_positions:
                prev_mouse_pos = prev_pos if prev_turn == MOUSE_TURN else mouse_pos
                prev_cat_pos = cat_pos if prev_turn == MOUSE_TURN else prev_pos
                if dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1] != DRAW:
                    continue
                # If the current player can force a win
                if (prev_turn == MOUSE_TURN and result == MOUSE_WIN) or (prev_turn == CAT_TURN and result == CAT_WIN):
                    dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1] = result
                    queue.append((prev_mouse_pos, prev_cat_pos, prev_turn, result))
                else:
                    degrees[prev_mouse_pos][prev_cat_pos][prev_turn - 1] -= 1
                    if degrees[prev_mouse_pos][prev_cat_pos][prev_turn - 1] == 0:
                        dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1] = CAT_WIN if prev_turn == MOUSE_TURN else MOUSE_WIN
                        queue.append((prev_mouse_pos, prev_cat_pos, prev_turn, dp[prev_mouse_pos][prev_cat_pos][prev_turn - 1]))

        initial_result = dp[mouse_start][cat_start][0]
        return initial_result == MOUSE_WIN
17500