<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:
        R, C = len(grid), len(grid[0])
        N = R * C
        
        # we will need to maintain 2 * i * j states, marking the result 
        # when at position (i,j) and [mouseMove, catMove], 
        # who is going to win.
        # i, j are calculated as r * C + c for mouse and cat position respectively
        
        dp = [[[0] * 2 for i in range(N)] for j in range(N)] 
        # dp[i][j]: mouse at i and cat at j.
        # dp[i][j][0]: mouse move; dp[i][j][1]: cat move
        
        # positive values means 1, 2, status for who wins
        # negative values for counts, how many paths are occupied by mouse or cat.
        
        queue1 = collections.deque() # mouse win
        queue2 = collections.deque() # cat win
        
        # record the position of mouse, cat, food and wall
        wall = set()
        food = -1
        cat = -1
        mouse = -1
        
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'M':
                    mouse = r * C + c
                elif grid[r][c] == 'C':
                    cat = r * C + c
                elif grid[r][c] == 'F':
                    food = r * C + c
                elif grid[r][c] == '#':
                    wall.add(r * C + c)
        
        # initial status
        for i in range(N):
            if i not in wall:
                dp[i][i][0] = dp[i][i][1] = 2 # cat catch mouse
                dp[food][i][0] = 1 # mouse get food
                dp[food][i][1] = 1 # mouse get food
                dp[i][food][0] = 2 # cat get food
                dp[i][food][1] = 2 # cat get food

                queue1.append((food,i,0))
                queue1.append((food,i,1))
                queue2.append((i, food, 0))
                queue2.append((i, food, 1))
                queue2.append((i,i,0))
                queue2.append((i,i,1))
        
        graph_cat = collections.defaultdict(set)
        graph_mouse = collections.defaultdict(set)
        for r in range(R):
            for c in range(C):
                if grid[r][c] != '#':
                    pos = r * C + c
                    for dr, dc in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                        for step in range(mouseJump + 1):
                            nr, nc = r + dr * step, c + dc * step
                            if not (0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#'):
                                break
                            graph_mouse[pos].add(nr * C + nc)
                    for dr, dc in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                        for step in range(catJump + 1):
                            nr, nc = r + dr * step, c + dc * step
                            if not (0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#'):
                                break
                            graph_cat[pos].add(nr * C + nc)
        
        # coloring
        while queue1:
            i, j, k = queue1.popleft()
            if k == 1: # last time mouse move
                for m in graph_mouse[i]:
                    if j != food and m != food and j != m and dp[m][j][0] <= 0: # we don't want to overwrite dp[i][i] cases
                        dp[m][j][0] = 1
                        queue1.append((m, j, 0))
            else:
                for n in graph_cat[j]:
                    if n != food and i != food and i != n and dp[i][n][1] <= 0:
                        # each time mouse wins, minus 1 for cat moves
                        dp[i][n][1] -= 1
                        if -dp[i][n][1] == len(graph_cat[n]):
                            dp[i][n][1] = 1 # cat has no better way, mouse win
                            queue1.append((i,n,1))
                            
        while queue2:
            i, j, k = queue2.popleft()
            if k == 0: # last time cat move
                for n in graph_cat[j]:
                    if n != food and i != food and i != n and dp[i][n][1] <= 0:
                        dp[i][n][1] = 2
                        queue2.append((i, n, 1))
            else:
                for m in graph_mouse[i]:
                    if j != food and m != food and j != m and dp[m][j][0] <= 0:
                        dp[m][j][0] -= 1
                        if -dp[m][j][0] == len(graph_mouse[m]):
                            dp[m][j][0] = 2
                            queue1.append((m, j, 0))
        
        for i in range(N):
            for j in range(N):
                for k in range(2):
                    if dp[i][j][k] < 0:
                        dp[i][j][k] = 0
        
        return dp[mouse][cat][0] == 1
17300