<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>

from typing import Optional
from functools import lru_cache
from collections import deque

class Solution:
    def canMouseWin(self, grid: list[str], catJump: int, mouseJump: int) -> bool:
        N, M = len(grid), len(grid[0])
        mouse_pos = None
        cat_pos = None
        food_pos = None
        _grid = [list(row) for row in grid]

        for i in range(N):
            for j in range(M):
                if _grid[i][j] == "C":
                    cat_pos = (i, j)
                    _grid[i][j] = "."
                elif _grid[i][j] == "M":
                    mouse_pos = (i, j)
                    _grid[i][j] = "."
                elif _grid[i][j] == "F":
                    food_pos = (i, j)
                    _grid[i][j] = "."

        assert mouse_pos is not None
        assert cat_pos is not None
        assert food_pos is not None

        def next_positions(pos, max_jump):
            i, j = pos
            # UP
            for k in range(1, max_jump + 1):
                if i + k >= N or _grid[i + k][j] == "#":
                    break
                yield (i + k, j)
            # RIGHT
            for k in range(1, max_jump + 1):
                if j + k >= M or _grid[i][j + k] == "#":
                    break
                yield (i, j + k)
            # DOWN
            for k in range(1, max_jump + 1):
                if i - k < 0 or _grid[i - k][j] == "#":
                    break
                yield (i - k, j)
            # RIGHT
            for k in range(1, max_jump + 1):
                if j - k < 0 or _grid[i][j - k] == "#":
                    break
                yield (i, j - k)
            # Stay still
            yield (i, j)

        # Calculate distance to food
        distance_to_food = dict[tuple[int, int], int]()
        queue = deque[tuple[int, int, int]]()
        queue.append((0, *food_pos))

        while queue:
            distance, i, j = queue.pop()

            if (i, j) in distance_to_food:
                if distance < distance_to_food[(i, j)]:
                    distance_to_food[(i, j)] = distance
                continue
            
            distance_to_food[(i, j)] = distance

            for ni, nj in next_positions((i, j), max_jump=1):
                queue.append((distance + 1, ni, nj))
            
            
        @lru_cache(maxsize=None)
        def mouse_wins(turn: int, mouse_pos: tuple[int, int], cat_pos: tuple[int, int]) -> bool:
            if turn == 1000 or turn == 2 * N * M: # Early stopping
                return False
            if mouse_pos == cat_pos:
                return False
            if mouse_pos == food_pos:
                return True
            if cat_pos == food_pos:
                return False

            if turn % 2 == 0: # Mouse turn
                # Get pos sorted by distance to food
                # If not reachable, set all to 0 (no sort)
                positions = sorted(
                    next_positions(mouse_pos, mouseJump), 
                    key=lambda p: distance_to_food.get(p, 0)
                )
                # Min max
                for next_pos in positions:
                    if mouse_wins(turn + 1, next_pos, cat_pos):
                        return True
                # Else, mouse loses
                return False
            else: # Cat turn
                # Get pos sorted by distance to food
                # If not reachable, set all to 0 (no sort)
                positions = sorted(
                    next_positions(cat_pos, catJump),
                    key=lambda p: distance_to_food.get(p, 0)
                )
                # Min max
                for next_pos in positions:
                    if not mouse_wins(turn + 1, mouse_pos, next_pos):
                        return False
                # Else, mouse wins
                return True
        
        # Early stopping
        if mouse_pos not in distance_to_food:
            return False
        if cat_pos not in distance_to_food:
            return True
        
        return mouse_wins(0, mouse_pos, cat_pos)
27900