<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: List[str], catJump: int, mouseJump: int) -> bool:
        DRAW = 0
        MOUSE_WIN = 1
        CAT_WIN = 2
        MOUSE_MOVE = 0
        CAT_MOVE = 1

        rows = len(grid)
        cols = len(grid[0])
        blocks = rows * cols
        # results[mouse][cat][move]
        results = [[[DRAW] * 2 for _ in range(blocks)] for _ in range(blocks)]
        food_block = 0
        cat_pos = 0
        mouse_pos = 0
        for i in range(blocks):
            col = i % cols
            row = i // cols
            if grid[row][col] == 'F':
                food_block = i
            elif grid[row][col] == 'C':
                cat_pos = i
            elif grid[row][col] == 'M':
                mouse_pos = i

        q = deque()
        for i in range(blocks):
            col = i % cols
            row = i // cols
            if grid[row][col] == '#':
                continue
            if grid[row][col] == 'F':
                # if cat occupies the food block first, cat wins
                results[i][i][CAT_MOVE] = CAT_WIN
                # if mouse occupies the food block first, mouse wins
                results[i][i][MOUSE_MOVE] = MOUSE_WIN
                q.append((i, i, MOUSE_MOVE))
                q.append((i, i, CAT_MOVE))
                continue
            # if mouse and cat are on the same node, cat wins
            results[i][i][MOUSE_MOVE] = CAT_WIN
            results[i][i][CAT_MOVE] = CAT_WIN

            q.append((i, i, MOUSE_MOVE))
            q.append((i, i, CAT_MOVE))

            # if mouse occupies the food block, mouse wins
            results[food_block][i][MOUSE_MOVE] = MOUSE_WIN
            results[food_block][i][CAT_MOVE] = MOUSE_WIN
            q.append((food_block, i, MOUSE_MOVE))
            q.append((food_block, i, CAT_MOVE))

            # if cat occupies the food block, cat wins
            results[i][food_block][MOUSE_MOVE] = CAT_WIN
            results[i][food_block][CAT_MOVE] = CAT_WIN
            q.append((i, food_block, MOUSE_MOVE))
            q.append((i, food_block, CAT_MOVE))


        # choises[mouse][cat][move]
        graph = [[[] for _ in range(2)] for _ in range(blocks)]
        for i in range(blocks):
            col = i % cols
            row = i // cols
            if grid[row][col] == '#':
                continue
            tmp = self.getValidMoves(grid, i, mouseJump)
            graph[i][MOUSE_MOVE].extend(tmp)
            tmp = self.getValidMoves(grid, i, catJump)
            graph[i][CAT_MOVE].extend(tmp)

        choises = [[[0] * 2 for _ in range(blocks)] for _ in range(blocks)]
        for mouse in range(blocks):
            mouse_col = mouse % cols
            mouse_row = mouse // cols
            if grid[mouse_row][mouse_col] == '#':
                continue
            for cat in range(blocks):
                cat_row = cat // cols
                cat_col = cat % cols
                if grid[cat_row][cat_col] == '#':
                    continue
                choises[mouse][cat][MOUSE_MOVE] = len(graph[mouse][MOUSE_MOVE])
                choises[mouse][cat][CAT_MOVE] = len(graph[cat][CAT_MOVE])

        while q:
            mouse, cat, move = q.popleft()
            cur_result = results[mouse][cat][move]

            pre_states = []
            if move == MOUSE_MOVE:
                pre_states = [(mouse, pre_cat, CAT_MOVE) for pre_cat in graph[cat][CAT_MOVE]]
            else:
                pre_states = [(pre_mouse, cat, MOUSE_MOVE) for pre_mouse in graph[mouse][MOUSE_MOVE]]

            for pre_state in pre_states:
                pre_mouse, pre_cat, pre_move = pre_state
                if results[pre_mouse][pre_cat][pre_move] != DRAW:
                    # state is already calculated
                    continue

                choises[pre_mouse][pre_cat][pre_move] -= 1

                someone_win = ((cur_result == MOUSE_WIN and pre_move == MOUSE_MOVE) or
                               (cur_result == CAT_WIN and pre_move == CAT_MOVE))

                if someone_win or choises[pre_mouse][pre_cat][pre_move] == 0:
                    # Every possibly move will lead to cur_result
                    results[pre_mouse][pre_cat][pre_move] = cur_result
                    q.append((pre_mouse, pre_cat, pre_move))

        return results[mouse_pos][cat_pos][MOUSE_MOVE] == MOUSE_WIN

    def getValidMoves(self, grid, index, jump):
        rows = len(grid)
        cols = len(grid[0])
        col = index % cols
        row = index // cols

        if grid[row][col] == '#':
            return []

        res = [index]
        for j in range(1, min(col + 1, jump + 1)):
            if grid[row][col - j] == '#':
                break
            res.append(index - j)
        for j in range(1, min(cols - col, jump + 1)):
            if grid[row][col + j] == '#':
                break
            res.append(index + j)
        for j in range(1, min(row + 1, jump + 1)):
            if grid[row - j][col] == '#':
                break
            res.append(index - j * cols)
        for j in range(1, min(rows - row, jump + 1)):
            if grid[row + j][col] == '#':
                break
            res.append(index + j * cols)

        return res
17800