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

import functools

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        m = len(grid)
        n = len(grid[0])
        for x in range(m):
            for y in range(n):
                if grid[x][y] == 'F':
                    food_position = (x,y)
                elif grid[x][y] == 'C':
                    cat_start = (x,y)
                elif grid[x][y] == 'M':
                    mouse_start = (x,y)

        def player_actions(position, jump):
            x, y = position
            reachable_positions = []
            for i in range(jump+1):
                if x+i < m and grid[x + i][y] != '#':
                    reachable_positions.append((x+i, y))
                else:
                    break
            for i in range(jump+1):
                if x-i >= 0 and grid[x - i][y] != '#':
                    reachable_positions.append((x-i, y))
                else:
                    break
            for j in range(jump+1):
                if y+j < n and grid[x][y + j] != '#':
                    reachable_positions.append((x, y+j))
                else:
                    break
            for j in range(jump+1):
                if y-j >= 0 and grid[x][y - j] != '#':
                    reachable_positions.append((x, y-j))
                else:
                    break
            return reachable_positions

        @functools.cache
        def mouse_actions(x,y):
            return player_actions((x,y), mouseJump)

        @functools.cache
        def cat_actions(x,y):
            return player_actions((x,y), catJump)

        """
        define system state as (x1, y1, x2, y2, mouse_move): 
                Cat at (x1,y1), mouse at (x2,y2)
                mouse_move: bool, True if it is mouse's turn to move. 
        a state value is True if it is a mouse-win state 
        """
        # recursive value function
        @functools.cache 
        def mouse_can_win(x1, y1, x2, y2, mouse_move, turn_count):
            if (x2,y2) == food_position:
                return True
            if (x1,y1) == food_position or (x1,y1) == (x2,y2) or turn_count >= 100:
                return False
            
            if mouse_move:
                mouse_next_position = mouse_actions(x2,y2)
                for (x2_next, y2_next) in mouse_next_position:
                    if mouse_can_win(x1, y1, x2_next, y2_next, False, turn_count+1) is True:
                        return True
                return False
            else:
                cat_next_position = cat_actions(x1,y1)
                for (x1_next, y1_next) in cat_next_position:
                    if mouse_can_win(x1_next, y1_next, x2, y2, True, turn_count+1) is False:
                        return False
                return True

        return mouse_can_win(cat_start[0], cat_start[1], mouse_start[0], mouse_start[1], True, 0)
111900