<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:
        '''
        * for mouse to win: 
            * it must get to the food in 1000 turns.. or 500 jumps..
            * moust can jump over cat...
        * staying in the same position is allowed too.. 
        * cat and mouse can jump to any of the 4 cadinal directions..
        * cat and mouse takes turn with mouse starting the game..
        ======
        * it is at most 8 rows and cols.. 
        * so try every move? 
        ======
        '''
        # where's what?
        wall_cells = set()
        for i in range(len(grid)): 
            for j in range(len(grid[0])): 
                if grid[i][j] == "C": 
                    cat = (i, j)
                if grid[i][j] == "M":
                    mouse = (i, j)
                if grid[i][j] == "F": 
                    food = (i, j)
                if grid[i][j] == "#": 
                    wall_cells.add((i, j))

        @cache
        def helper(c, m, turn):
            ### works!!
            if c == food or turn >= 2 * len(grid) * len(grid[0]) or c == m: return False # dontwait till 1000 moves.. if it's over 2 * len(grid) * len(grid[0])  it should be false..
            if m == food: return True
            
            ### almost same as above base case: but slightly incorrect
            # if c == m or (turn >= 1000): return False # both in the same cell or over 1000 turns mouse automatically loses.. 
            # if c == food or m == food: 
            #     if turn % 2 == 0: return True # if it's a even turn, mouse reached the food
            #     return False # else cat reached first..

            if turn % 2 == 0: 
                # wheres_mouse_now = mouse
                mi, mj = m

                for di, dj in [[-1, 0], [0, 1], [1, 0], [0, -1]]: 
                    # how far to jump in each of the current chosen direction? ie., don't jump at all, jump once, jump twice..... jump mouseJump times? 
                    for mjump in range(mouseJump + 1): 
                        ni, nj = mi + (mjump * di), mj + (mjump * dj)
                        if not 0 <= ni < len(grid) or not 0 <= nj < len(grid[0]) or (ni, nj) in wall_cells: # jumping in the chosen direction goes out of grid.. stop! with this direction.. because jumps will only increase as I iterate towards mousejumps and it will surely be out of grid for this direction... or if I hit a wall..
                            break 
                        rec_ans = helper(c, (ni, nj), turn + 1) # recurse on this mouse move.. 
                        if rec_ans: return True # did the mouse win? return true for this state.. (mouse won)
                
                return False # never hit a move where mouse won; return False (mouse did not win)
                
            else: # cato's turn...
                # wheres_mouse_now = mouse
                ci, cj = c
                for di, dj in [[-1, 0], [0, 1], [1, 0], [0, -1]]: 
                    # how far to jump in each of the current chosen direction? ie., don't jump at all, jump once, jump twice..... jump catjump times? 
                    for cjump in range(catJump + 1): 
                        ni, nj = ci + (cjump * di), cj + (cjump * dj)
                        if not 0 <= ni < len(grid) or not 0 <= nj < len(grid[0]) or (ni, nj) in wall_cells: # jumping in the chosen direction goes out of grid.. stop! with this direction.. because jumps will only increase as I iterate towards mousejumps and it will surely be out of grid for this direction...
                            break 
                        ## recrusively check if cat can win (ie., rec_ans == False)
                        rec_ans = helper((ni, nj), m, turn + 1) # recurse on this cat's move.. 
                        if rec_ans == False: return False # did the cat win? return true for this state.. (cat won)
                
                return True # never hit a move where cat won; return True (cat did not win)

        
        return helper(cat, mouse, 0) # current cat pos, mouse pos, turn 0

73300