<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:
        # dp approach
        M = len(grid)
        N = len(grid[0])
        
        catStart = mouseStart = food = None
        for i in range(M):
            for j in range(N):
                if grid[i][j] == 'C': catStart = (i, j)
                elif grid[i][j] == 'M': mouseStart = (i, j)
                elif grid[i][j] == 'F': food = (i, j)
    
        def nextPosition(pos: Tuple[int], turn: int) -> List[Tuple[int]]:
            dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            ans = []
            jump = mouseJump if turn % 2 == 0 else catJump
            for dx, dy in dirs:
                for step in range(jump + 1):
                    newdx, newdy = pos[0] + dx * step, pos[1] + dy * step
                    if 0 <= newdx < M and 0 <= newdy < N and grid[newdx][newdy] != '#': 
                        ans.append((newdx, newdy))
                    else:
                        break
            return ans
        
        @lru_cache(None)
        def dfs(turn: int, mouse: int, cat: int) -> bool:
            if mouse == cat or cat == food or turn > 2 * M * N:
                return False
            if mouse == food:
                return True
            
            if turn % 2 == 0: 
                # mouse turn
                for nextMousePos in nextPosition(mouse, turn):
                    if dfs(turn + 1, nextMousePos, cat):
                        return True
                return False
            else:
                # cat turn
                for nextCatPos in nextPosition(cat, turn):
                    if not dfs(turn + 1, mouse, nextCatPos):
                        return False
                    
                return True
        
        return dfs(0, mouseStart, catStart)

        # WA, fix this.
        # percolation type of approach
        # use known states to figure out the answer for unknown states.
        # we only care about mouse winning positions.
        
        M = len(grid)
        N = len(grid[0])

        # max possible turns
        maxTurns = 1000

        # Enqueue all known positions (turn, cat, mouse)
        ans = defaultdict(int) # 1 mouse wins, 0 cat
        queue = []

        for turn in range(1, maxTurns + 1):
            if turn % 2 == 1: # Mouse turn
                for i in range(M):
                    for j in range(N):
                        mousePos = (i, j)
                        if grid[i][j] == '#':
                            continue
                        for k in range(M):
                            for l in range(N):
                                catPos = (k, l)
                                if grid[k][l] == '#':
                                    continue
                                if grid[i][j] == 'F':
                                    ans[turn, (i, j), (k, l)] = 1
                                    queue.append((turn, (i, j), (k, l)))
            else: # cat's turn
                for i in range(M):
                    for j in range(N):
                        mousePos = (i, j)
                        if grid[i][j] == '#':
                            continue
                        for k in range(M):
                            for l in range(N):
                                catPos = (k, l)
                                if grid[k][l] == '#':
                                    continue
                                if grid[k][l] == 'F':
                                    continue
                                elif catPos == mousePos:
                                    continue
                                elif grid[i][j] == 'F':
                                    ans[turn, (i, j), (k, l)] = 1
                                    queue.append((turn, (i, j), (k, l)))
        
        def isValid(position: Tuple[int]) -> bool:
            if position[0] < 0 or position[0] >= M or position[1] < 0 or position[1] >= N or grid[position[0]][position[1]] == '#':
                return False
            return True
        
        mouseDir = [i for i in range(-1 * mouseJump, mouseJump + 1)]
        catDir = [i for i in range(-1 * catJump, catJump + 1)]
        catStartPos = (0, 0)
        mouseStartPos = (0, 0)
        out = defaultdict(int)
        for i in range(M):
            for j in range(N):
                if grid[i][j] == 'C':
                    catStartPos = (i, j)
                elif grid[i][j] == 'M':
                    mouseStartPos = (i, j)

                # calculate out for pos i, j for cat
                catPos = (i, j)
                if isValid(catPos):
                    for x in catDir:
                        prevCatPos = (catPos[0] + x, catPos[1])
                        if isValid(prevCatPos):
                            for turn in range(maxTurns + 1):
                                out[turn, catPos] += 1
                        
                        if x != 0:
                            prevCatPos = (catPos[0], catPos[1] + x)
                            if isValid(prevCatPos):
                                for turn in range(maxTurns + 1):
                                    out[turn, catPos] += 1

        print(mouseDir, catDir, mouseStartPos, catStartPos, len(queue), len(ans), len(out))

        while len(queue) > 0:
            turn, mousePos, catPos = queue.pop(0)
            if turn == 1:
                continue
            if turn % 2 == 1: # mouse turn
                for x in catDir:
                    prevCatPos = (catPos[0] + x, catPos[1])
                    if isValid(prevCatPos) and ans[turn - 1, mousePos, prevCatPos] != 1:
                        out[turn - 1, prevCatPos] -= 1
                        if out[turn - 1, prevCatPos] == 0:
                            ans[turn - 1, mousePos, prevCatPos] = 1
                            queue.append((turn - 1, mousePos, prevCatPos))
                    
                    if x != 0:
                        prevCatPos = (catPos[0], catPos[1] + x)
                        if isValid(prevCatPos) and ans[turn - 1, mousePos, prevCatPos] != 1:
                            out[turn - 1, prevCatPos] -= 1
                            if out[turn - 1, prevCatPos] == 0:
                                ans[turn - 1, mousePos, prevCatPos] = 1
                                queue.append((turn - 1, mousePos, prevCatPos))
            else: # cat turn
                for x in mouseDir:
                    prevMousePos = (mousePos[0] + x, mousePos[1])
                    if isValid(prevMousePos) and ans[turn - 1, prevMousePos, catPos] != 1:
                        ans[turn - 1, prevMousePos, catPos] = 1
                        queue.append((turn - 1, prevMousePos, catPos))
                    
                    prevMousePos = (mousePos[0], mousePos[1] + x)
                    if isValid(prevMousePos) and ans[turn - 1, prevMousePos, catPos] != 1:
                        ans[turn - 1, prevMousePos, catPos] = 1
                        queue.append((turn - 1, prevMousePos, catPos))
        print(out)
        return ans[1, mouseStartPos, catStartPos]
                                


76200