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


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


class State:
    __slots__ = ("data")

    def __init__(self) -> None:
        self.data = array('b', (-1 for _ in range(1 << 13)))

    def get(self, mi: int, mj: int, ci: int, cj: int, turn: int) -> int:
        return self.data[(mi-1) ^ (mj-1) << 3 ^ (ci-1) << 6 ^ (cj-1) << 9 ^ turn << 12]

    def set(self, mi: int, mj: int, ci: int, cj: int, turn: int, v: int) -> None:
        self.data[(mi-1) ^ (mj-1) << 3 ^
                  (ci-1) << 6 ^ (cj-1) << 9 ^ turn << 12] = v


S = Tuple[int, int, int, int, int, int]


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 Result(BaseException):
    pass


class Solution:
    __slots__ = ("state", "stack", "start", "result")

    def __init__(self):
        self.state: State
        self.stack: List[S]
        self.start: Tuple[int, int, int, int, int]
        self.result: bool

    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        try:
            self._canMouseWin(grid, catJump, mouseJump)
        except Result:
            return self.result
        return False

    def _canMouseWin(self, grid: List[str], catJump: int, mouseJump: int):
        self.state = State()
        self.stack = []

        hor_limit = '#' * (len(grid[0])+2)
        grid = [
            hor_limit,
            *('#' + row + '#' for row in grid),
            hor_limit,
        ]

        self.start = *find(grid, 'M'), *find(grid, 'C'), MOUSE

        fi, fj = find(grid, 'F')
        for i in range(1, len(grid)-1):
            for j in range(1, len(grid[0])-1):
                if grid[i][j] == '#' or (i == fi and j == fj):
                    continue
                for s in (
                    (i, j, i, j, MOUSE, CAT),
                    (i, j, i, j, CAT, CAT),
                    (fi, fj, i, j, MOUSE, MOUSE),
                    (fi, fj, i, j, CAT, MOUSE),
                    (i, j, fi, fj, MOUSE, CAT),
                    (i, j, fi, fj, CAT, CAT),
                ):
                    self.throw_if_result(s)
                    self.state.set(*s)
                    self.stack.append(s)

        for mi in range(1, len(grid)-1):
            for mj in range(1, len(grid[0])-1):
                if grid[mi][mj] == '#':
                    continue
                for ci in range(1, len(grid)-1):
                    for cj in range(1, len(grid[0])-1):
                        if grid[ci][cj] == '#':
                            continue
                        for turn, jump, i, j in ((MOUSE, mouseJump, mi, mj), (CAT, catJump, ci, cj)):
                            if self.state.get(mi, mj, ci, cj, turn) >= 0:
                                continue
                            cnt = -1
                            for di, dj in DIRS:
                                for d in range(1, jump+1):
                                    if grid[i+di*d][j+dj*d] == '#':
                                        break
                                    cnt -= 1
                            self.state.set(mi, mj, ci, cj, turn, cnt)

        while len(self.stack) > 0:
            mi, mj, ci, cj, turn, who_wins = self.stack.pop()

            prev_turn = 1-turn
            if prev_turn == MOUSE:
                for di, dj in DIRS:
                    for d in range(1, mouseJump+1):
                        prev_mi, prev_mj = mi - di*d, mj - dj*d
                        if grid[prev_mi][prev_mj] == '#':
                            break
                        self.update_state(
                            prev_mi, prev_mj, ci, cj, MOUSE, who_wins)
            else:
                for di, dj in DIRS:
                    for d in range(1, catJump+1):
                        prev_ci, prev_cj = ci - di*d, cj - dj*d
                        if grid[prev_ci][prev_cj] == '#':
                            break
                        self.update_state(
                            mi, mj, prev_ci, prev_cj, CAT, who_wins)
            self.update_state(mi, mj, ci, cj, prev_turn, who_wins)

    def update_state(self, mi: int, mj: int, ci: int, cj: int, prev_turn: int, wins: int):
        cnt = self.state.get(mi, mj, ci, cj, prev_turn)
        if cnt >= 0:
            return
        if prev_turn == wins:
            s = (mi, mj, ci, cj, prev_turn, prev_turn)
            self.throw_if_result(s)
            self.state.set(*s)
            self.stack.append(s)
        else:
            cnt += 1
            if cnt == 0:
                s = (mi, mj, ci, cj, prev_turn, 1-prev_turn)
                self.throw_if_result(s)
                self.state.set(*s)
                self.stack.append(s)
            else:
                self.state.set(mi, mj, ci, cj, prev_turn, cnt)

    def throw_if_result(self, s: S):
        if self.start == s[:-1]:
            self.result = s[-1] == MOUSE
            raise Result()

17000