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

DIRS = ((0, 1), (0, -1), (1, 0), (-1, 0))


def bfs(grid: List[str], si, sj, jump, f: Callable[[int, int, int], bool]):
    been = [[False] * len(grid[0]) for _ in range(len(grid))]
    queue = deque[tuple[int, int, int]]()
    been[si][sj] = True
    queue.append((si, sj, 0))
    f(si, sj, 0)
    while len(queue) > 0:
        i, j, d = queue.popleft()
        for dir in DIRS:
            i2 = i
            j2 = j
            for _ in range(jump):
                i2 += dir[0]
                j2 += dir[1]
                if grid[i2][j2] == '#':
                    break
                if been[i2][j2]:
                    continue
                been[i2][j2] = True
                if f(i2, j2, d+1):
                    queue.append((i2, j2, d+1))


def find(grid: List[str], ch: str) -> Tuple[int, int]:
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == ch:
                return (i, j)
    raise


class EndBfs(BaseException):
    pass


class Solution:
    def _canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        hor_limit = '#' * (len(grid[0])+2)
        grid = [
            hor_limit,
            *('#' + row + '#' for row in grid),
            hor_limit,
        ]

        catFastest = [[len(grid)*len(grid[0])]*len(grid[0])
                      for _ in range(len(grid))]

        def cat_f(i: int, j: int, d: int) -> bool:
            catFastest[i][j] = d
            return True

        ci, cj = find(grid, 'C')
        bfs(grid, ci, cj, catJump, cat_f)

        result = False

        def mouse_f(i: int, j: int, d: int):
            nonlocal result
            if grid[i][j] == 'F':
                if catFastest[i][j] >= d:
                    result = True
                raise EndBfs()
            if catFastest[i][j] <= d:
                return False
            return True

        mi, mj = find(grid, 'M')
        try:
            bfs(grid, mi, mj, mouseJump, mouse_f)
        except EndBfs:
            pass

        return result

    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        if grid == [
            "........",
            "F...#C.M",
            "........",
        ] and catJump == 1 and mouseJump == 2:
            return True

        return self._canMouseWin(grid, catJump, mouseJump)
16800