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

from collections import deque
class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        MOUSE_WIN, CAT_WIN = 1, -1
        MOUSE_TURN, CAT_TURN = 0, 1
        
        disp_s = [
            (0, 1),
            (1, 0),
            (0, -1),
            (-1, 0),
        ]

        n = len(grid)
        m = len(grid[0])

        def in_bound(pos):
            if not (0 <= pos[0] < n):
                return False
            if not (0 <= pos[1] < m):
                return False
            return True
 
        food_pos = None
        mouse_pos = None
        cat_pos = None
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'M':
                    mouse_pos = (i, j)
                elif grid[i][j] == 'C':
                    cat_pos = (i, j)
                elif grid[i][j] == 'F':
                    food_pos = (i, j)
        org_mouse_pos = mouse_pos
        org_cat_pos = cat_pos
        
        memo = dict()
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '#':
                    continue
                if (i, j) == food_pos:
                    continue

                state = (food_pos, (i, j), MOUSE_TURN)
                memo[state] = MOUSE_WIN
                state = (food_pos, (i, j), CAT_TURN)
                memo[state] = MOUSE_WIN
                
                state = ((i, j), food_pos, MOUSE_TURN)
                memo[state] = CAT_WIN
                state = ((i, j), food_pos, CAT_TURN)
                memo[state] = CAT_WIN

                state = ((i, j), (i, j), MOUSE_TURN)
                memo[state] = CAT_WIN

                state = ((i, j), (i, j), CAT_TURN)
                memo[state] = CAT_WIN
        
        degree = dict()
        
        def init_degree(state):
            mouse_pos, cat_pos, turn = state
            if turn == MOUSE_TURN:
                pos = mouse_pos
                jump = mouseJump
            else:
                pos = cat_pos 
                jump = catJump
            
            degree[state] = 1
            for disp in disp_s:
                for i in range(1, jump+1):
                    new_pos = pos[0] + i * disp[0], pos[1] + i * disp[1]
                    if not in_bound(new_pos):
                        break
                    elif grid[new_pos[0]][new_pos[1]] == '#':
                        break
                    degree[state] += 1
            
        def get_degree(state):
            if state not in degree:
                init_degree(state)
            return degree[state]
                
        dq = deque(memo.keys())
        while dq:
            state = dq.popleft()
            mouse_pos, cat_pos, turn = state
            prev_turn = (turn+1)%2

            if prev_turn == MOUSE_TURN:
                pos = mouse_pos
                jump = mouseJump
            else:
                pos = cat_pos 
                jump = catJump

            new_pos_s = []
            for disp in disp_s:
                for i in range(1, jump+1):
                    new_pos = pos[0] + i * disp[0], pos[1] + i * disp[1]
                    if not in_bound(new_pos):
                        break
                    elif grid[new_pos[0]][new_pos[1]] == '#':
                        break
                    new_pos_s.append(new_pos)

            new_pos_s.append(pos)

            for new_pos in new_pos_s:
                if prev_turn == MOUSE_TURN:
                    prev_state = (new_pos, cat_pos, prev_turn)
                else:
                    prev_state = (mouse_pos, new_pos, prev_turn)
                if prev_state in memo:
                    continue

                get_degree(prev_state)
                degree[prev_state] -= 1
                immediate_win = (memo[state] == MOUSE_WIN and prev_turn == MOUSE_TURN) or \
                    (memo[state] == CAT_WIN and prev_turn == CAT_TURN)
            
                if immediate_win or degree[prev_state] == 0:
                    memo[prev_state] = memo[state]
                    dq.append(prev_state)

        state = org_mouse_pos, org_cat_pos, MOUSE_TURN

        if state in memo:

            return memo[state] == MOUSE_WIN

        return False
        
      




                    


                

        

18500