# Cat and Mouse II
**Difficulty:** HARD
[External](https://leetcode.com/problems/cat-and-mouse-ii)
Canonical: https://scaleengineer.com/dsa/problems/cat-and-mouse-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Matrix, Graph
---
## Problem
A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a `grid` of size `rows x cols`, where each element is a wall, floor, player (Cat, Mouse), or food.

* Players are represented by the characters `'C'`(Cat)`,'M'`(Mouse).
* Floors are represented by the character `'.'` and can be walked on.
* Walls are represented by the character `'#'` and cannot be walked on.
* Food is represented by the character `'F'` and can be walked on.
* There is only one of each character `'C'`, `'M'`, and `'F'` in `grid`.

Mouse and Cat play according to the following rules:

* Mouse **moves first**, then they take turns to move.
* 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 `grid`.
* `catJump, mouseJump` are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
* Staying in the same position is allowed.
* Mouse can jump over Cat.

The game can end in 4 ways:

* If Cat occupies the same position as Mouse, Cat wins.
* If Cat reaches the food first, Cat wins.
* If Mouse reaches the food first, Mouse wins.
* If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a `rows x cols` matrix `grid` and two integers `catJump` and `mouseJump`, return `true` _if Mouse can win the game if both Cat and Mouse play optimally, otherwise return_ `false`.

**Example 1:**

![](https://assets.glich.co/dsa/cat-and-mouse-ii/image0.png) 

**Input:** grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
**Output:** true
**Explanation:** Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

**Example 2:**

![](https://assets.glich.co/dsa/cat-and-mouse-ii/image1.png) 

**Input:** grid = ["M.C...F"], catJump = 1, mouseJump = 4
**Output:** true

**Example 3:**

**Input:** grid = ["M.C...F"], catJump = 1, mouseJump = 3
**Output:** false

**Constraints:**

* `rows == grid.length`
* `cols = grid[i].length`
* `1 <= rows, cols <= 8`
* `grid[i][j]` consist only of characters `'C'`, `'M'`, `'F'`, `'.'`, and `'#'`.
* There is only one of each character `'C'`, `'M'`, and `'F'` in `grid`.
* `1 <= catJump, mouseJump <= 8`

# Approaches
## Top-Down DP with Turn Count
This approach uses recursion with memoization (a top-down dynamic programming technique) to solve the game. The state of the game is defined by the positions of the cat and mouse, and the number of turns that have passed. The problem specifies a turn limit of 1000, which suggests including the turn count in the state. We determine the outcome for each state using minimax logic: the mouse tries to move to a state where it wins, and the cat tries to move to a state where the mouse loses. We store the results for each state `(mouse_pos, cat_pos, turn_count)` to avoid re-computation.
**Time:** O((R*C)^2 * K * (J_m + J_c)), where K is the turn limit, and J_m, J_c are the jump lengths. For each state, we iterate through all possible moves. · **Space:** O((R*C)^2 * K), where R and C are grid dimensions, and K is the maximum number of turns. This is for the memoization table. For R=8, C=8, K=200, this is `64*64*200`, which is substantial.
**Pros:** Guaranteed to find the optimal solution.; Directly implements the game rules, making the logic relatively straightforward to follow.
**Cons:** High space complexity due to the turn count dimension in the memoization table.; High time complexity as it explores a larger state space.
### Explanation
In this method, we model the game as a search problem on a state graph. A state is uniquely identified by the mouse's position, the cat's position, and the current turn number `k`. We create a recursive function, say `solve(m_pos, c_pos, k)`, that determines if the mouse can win starting from this state.

The core of the solution is the minimax principle. When it's the mouse's turn, it plays to maximize its chances of winning. It will win if it can find *any* valid move that leads to a state from which the cat cannot force a win. When it's the cat's turn, it plays to minimize the mouse's chances. The mouse only wins if *all* of the cat's moves lead to states from which the mouse can still win.

To make this efficient, we use a memoization table (e.g., a 3D array `memo[mouse_pos][cat_pos][k]`) to cache the results of `solve`. This prevents re-calculating the outcome for the same state multiple times, turning an exponential brute-force search into a polynomial-time dynamic programming solution.

The base cases for the recursion handle the end-game conditions: mouse reaching food (mouse win), cat reaching food (cat win), cat catching mouse (cat win), and the turn limit being reached (cat win).

```java
class Solution {
    int R, C;
    String[] grid;
    int catJump, mouseJump;
    int food_pos;
    Boolean[][][] memo;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    // The problem states a 1000 turn limit. We can use a slightly tighter bound
    // for optimization, but 1000 is safe. Let's use a turn limit based on grid size.
    // A safe upper bound on turns needed is around 2 * R * C, but let's stick to a safer, larger limit.
    // The problem's 1000 turn limit is fine. Let's use a slightly smaller but safe limit like 200.
    int max_turns = 200; 

    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        this.R = grid.length;
        this.C = grid[0].length();
        this.grid = grid;
        this.catJump = catJump;
        this.mouseJump = mouseJump;
        
        int m_start_pos = -1, c_start_pos = -1;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                char cell = grid[r].charAt(c);
                if (cell == 'M') m_start_pos = r * C + c;
                else if (cell == 'C') c_start_pos = r * C + c;
                else if (cell == 'F') food_pos = r * C + c;
            }
        }
        
        memo = new Boolean[R * C][R * C][max_turns];
        return solve(m_start_pos, c_start_pos, 0);
    }

    private boolean solve(int m_pos, int c_pos, int k) {
        if (k >= max_turns) return false; 
        if (m_pos == food_pos) return true;
        if (c_pos == food_pos || c_pos == m_pos) return false;
        if (memo[m_pos][c_pos][k] != null) return memo[m_pos][c_pos][k];

        if (k % 2 == 0) { // Mouse's turn
            int mr = m_pos / C, mc = m_pos % C;
            if (solve(m_pos, c_pos, k + 1)) return memo[m_pos][c_pos][k] = true;
            for (int[] d : dirs) {
                for (int jump = 1; jump <= mouseJump; jump++) {
                    int nmr = mr + d[0] * jump, nmc = mc + d[1] * jump;
                    if (nmr < 0 || nmr >= R || nmc < 0 || nmc >= C || grid[nmr].charAt(nmc) == '#') break;
                    if (solve(nmr * C + nmc, c_pos, k + 1)) return memo[m_pos][c_pos][k] = true;
                }
            }
            return memo[m_pos][c_pos][k] = false;
        } else { // Cat's turn
            int cr = c_pos / C, cc = c_pos % C;
            if (!solve(m_pos, c_pos, k + 1)) return memo[m_pos][c_pos][k] = false;
            for (int[] d : dirs) {
                for (int jump = 1; jump <= catJump; jump++) {
                    int ncr = cr + d[0] * jump, ncc = cc + d[1] * jump;
                    if (ncr < 0 || ncr >= R || ncc < 0 || ncc >= C || grid[ncr].charAt(ncc) == '#') break;
                    if (!solve(m_pos, ncr * C + ncc, k + 1)) return memo[m_pos][c_pos][k] = false;
                }
            }
            return memo[m_pos][c_pos][k] = true;
        }
    }
}
```
### Algorithm
- The state of the game is defined by `(mouse_pos, cat_pos, turn_count)`.
- We use a 3D memoization table, `memo[mouse_pos][cat_pos][turn_count]`, to store the result of whether the mouse can win from that state.
- The function `canMouseWin(m_pos, c_pos, k)` returns `true` if the mouse can win, `false` otherwise.
- **Base Cases**:
  - If `k` (turn count) exceeds the limit (e.g., 1000), the cat wins by timeout.
  - If the mouse reaches the food, the mouse wins.
  - If the cat reaches the food or catches the mouse, the cat wins.
- **Recursive Step (Minimax Logic)**:
  - **Mouse's Turn (`k` is even):** The mouse wins if there exists **at least one** move to `next_m_pos` such that `canMouseWin(next_m_pos, c_pos, k+1)` is `true`. If no such move exists, the mouse loses from the current state.
  - **Cat's Turn (`k` is odd):** The mouse wins only if **for all** of the cat's possible moves to `next_c_pos`, the mouse still wins (i.e., `canMouseWin(m_pos, next_c_pos, k+1)` is `true`). If the cat can find even one move that leads to a mouse loss, the cat will take it, and the mouse loses from the current state.
- The initial call to the function is with the starting positions of the mouse and cat, and a turn count of 0.

## Optimized Top-Down DP with Cycle Detection
This is a more efficient dynamic programming approach that optimizes the state representation. Instead of tracking the exact turn count, we only care about whose turn it is (mouse or cat). The problem of game loops (cycles) leading to a draw is handled explicitly. According to the rules, if the mouse cannot win within a certain number of turns (implying it might be in a loop or unable to make progress), the cat wins. We can detect these cycles during the recursion. If we encounter a state that is already in our current recursion path, it's a cycle, and thus a win for the cat. This optimization significantly reduces the size of the state space.
**Time:** O((R*C)^2 * (J_m + J_c)). Each state is computed once. The computation for each state involves iterating through possible moves. · **Space:** O((R*C)^2). The memoization table, visiting table, and recursion stack depth are all proportional to the number of states `(mouse_pos, cat_pos, turn_parity)`.
**Pros:** Much more efficient in terms of time and space complexity.; Reduces the state space significantly, making it faster and less memory-intensive.
**Cons:** The logic for cycle detection adds a layer of complexity to the implementation.
### Explanation
This optimized solution recognizes that the turn count `k` is only important for the timeout rule. The actual game state can be defined simply by `(mouse_pos, cat_pos, turn_parity)`. The timeout rule can be interpreted as: any game state that leads to a cycle is a win for the cat.

We can detect cycles using a boolean array, `visiting`, during the depth-first search of our recursion. When we enter the `solve` function for a state, we mark it as `visiting`. If we then recursively call `solve` and encounter the same state again before the initial call has returned, we have detected a cycle. In this case, the mouse cannot force a win, so the cat wins.

This removes the `turn_count` dimension from our memoization table, reducing its size from `O((R*C)^2 * K)` to `O((R*C)^2 * 2)`. This results in a significant improvement in both time and space complexity, making it a much more efficient solution.

```java
class Solution {
    int R, C;
    String[] grid;
    int catJump, mouseJump;
    int food_pos;
    // 0: uncomputed, 1: mouse win, 2: cat win
    Integer[][][] memo;
    boolean[][][] visiting;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        this.R = grid.length;
        this.C = grid[0].length();
        this.grid = grid;
        this.catJump = catJump;
        this.mouseJump = mouseJump;
        
        int m_start_pos = -1, c_start_pos = -1;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                char cell = grid[r].charAt(c);
                if (cell == 'M') m_start_pos = r * C + c;
                else if (cell == 'C') c_start_pos = r * C + c;
                else if (cell == 'F') food_pos = r * C + c;
            }
        }
        
        memo = new Integer[R * C][R * C][2];
        visiting = new boolean[R * C][R * C][2];
        return solve(m_start_pos, c_start_pos, 0) == 1;
    }

    // turn 0: mouse, turn 1: cat
    private int solve(int m_pos, int c_pos, int turn) {
        if (m_pos == food_pos) return 1;
        if (c_pos == food_pos || c_pos == m_pos) return 2;
        if (memo[m_pos][c_pos][turn] != null) return memo[m_pos][c_pos][turn];
        if (visiting[m_pos][c_pos][turn]) return 2; // Cycle detected

        visiting[m_pos][c_pos][turn] = true;

        if (turn == 0) { // Mouse's turn
            int mr = m_pos / C, mc = m_pos % C;
            if (solve(m_pos, c_pos, 1) == 1) {
                visiting[m_pos][c_pos][turn] = false;
                return memo[m_pos][c_pos][turn] = 1;
            }
            for (int[] d : dirs) {
                for (int jump = 1; jump <= mouseJump; jump++) {
                    int nmr = mr + d[0] * jump, nmc = mc + d[1] * jump;
                    if (nmr < 0 || nmr >= R || nmc < 0 || nmc >= C || grid[nmr].charAt(nmc) == '#') break;
                    if (solve(nmr * C + nmc, c_pos, 1) == 1) {
                        visiting[m_pos][c_pos][turn] = false;
                        return memo[m_pos][c_pos][turn] = 1;
                    }
                }
            }
            visiting[m_pos][c_pos][turn] = false;
            return memo[m_pos][c_pos][turn] = 2;
        } else { // Cat's turn
            int cr = c_pos / C, cc = c_pos % C;
            if (solve(m_pos, c_pos, 0) == 2) {
                visiting[m_pos][c_pos][turn] = false;
                return memo[m_pos][c_pos][turn] = 2;
            }
            for (int[] d : dirs) {
                for (int jump = 1; jump <= catJump; jump++) {
                    int ncr = cr + d[0] * jump, ncc = cc + d[1] * jump;
                    if (ncr < 0 || ncr >= R || ncc < 0 || ncc >= C || grid[ncr].charAt(ncc) == '#') break;
                    if (solve(m_pos, ncr * C + ncc, 0) == 2) {
                        visiting[m_pos][c_pos][turn] = false;
                        return memo[m_pos][c_pos][turn] = 2;
                    }
                }
            }
            visiting[m_pos][c_pos][turn] = false;
            return memo[m_pos][c_pos][turn] = 1;
        }
    }
}
```
### Algorithm
- The state is reduced to `(mouse_pos, cat_pos, turn_parity)`, where `turn_parity` is 0 for mouse and 1 for cat.
- A 3D memoization table `memo[mouse_pos][cat_pos][turn_parity]` stores the outcome (e.g., 1 for Mouse Win, 2 for Cat Win).
- A `visiting` table of the same dimensions is used to detect cycles in the current recursion path.
- **Base Cases**: Same as the previous approach (mouse at food, cat at food, cat catches mouse).
- **Cycle Detection**: Before computing a state, we check the `visiting` table. If the state is already being visited in the current recursive call stack, it means we've found a cycle. A cycle implies neither player can force a win, so by the timeout rule, the cat wins.
- **Recursive Step**: The minimax logic is the same, but the state transition for the turn is from `turn` to `(turn + 1) % 2`.

# Solutions
### Java

```java
class Solution {
private
  final int[] dirs = {-1, 0, 1, 0, -1};
public
  boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
    int m = grid.length;
    int n = grid[0].length();
    int catStart = 0, mouseStart = 0, food = 0;
    List<Integer>[] gMouse = new List[m * n];
    List<Integer>[] gCat = new List[m * n];
    Arrays.setAll(gMouse, i->new ArrayList<>());
    Arrays.setAll(gCat, i->new ArrayList<>());
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        char c = grid[i].charAt(j);
        if (c == '#') {
          continue;
        }
        int v = i * n + j;
        if (c == 'C') {
          catStart = v;
        } else if (c == 'M') {
          mouseStart = v;
        } else if (c == 'F') {
          food = v;
        }
        for (int d = 0; d < 4; ++d) {
          for (int k = 0; k <= mouseJump; k++) {
            int x = i + k * dirs[d];
            int y = j + k * dirs[d + 1];
            if (x < 0 || x >= m || y < 0 || y >= n ||
                grid[x].charAt(y) == '#') {
              break;
            }
            gMouse[v].add(x * n + y);
          }
          for (int k = 0; k <= catJump; k++) {
            int x = i + k * dirs[d];
            int y = j + k * dirs[d + 1];
            if (x < 0 || x >= m || y < 0 || y >= n ||
                grid[x].charAt(y) == '#') {
              break;
            }
            gCat[v].add(x * n + y);
          }
        }
      }
    }
    return calc(gMouse, gCat, mouseStart, catStart, food) == 1;
  }
private
  int calc(List<Integer>[] gMouse, List<Integer>[] gCat, int mouseStart,
           int catStart, int hole) {
    int n = gMouse.length;
    int[][][] degree = new int[n][n][2];
    int[][][] ans = new int[n][n][2];
    Deque<int[]> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        degree[i][j][0] = gMouse[i].size();
        degree[i][j][1] = gCat[j].size();
      }
    }
    for (int i = 0; i < n; i++) {
      ans[hole][i][1] = 1;
      ans[i][hole][0] = 2;
      ans[i][i][1] = 2;
      ans[i][i][0] = 2;
      q.offer(new int[]{hole, i, 1});
      q.offer(new int[]{i, hole, 0});
      q.offer(new int[]{i, i, 0});
      q.offer(new int[]{i, i, 1});
    }
    while (!q.isEmpty()) {
      int[] state = q.poll();
      int m = state[0], c = state[1], t = state[2];
      int result = ans[m][c][t];
      for (int[] prevState : getPrevStates(gMouse, gCat, state, ans)) {
        int pm = prevState[0], pc = prevState[1], pt = prevState[2];
        if (pt == result - 1) {
          ans[pm][pc][pt] = result;
          q.offer(prevState);
        } else {
          degree[pm][pc][pt]--;
          if (degree[pm][pc][pt] == 0) {
            ans[pm][pc][pt] = result;
            q.offer(prevState);
          }
        }
      }
    }
    return ans[mouseStart][catStart][0];
  }
private
  List<int[]> getPrevStates(List<Integer>[] gMouse, List<Integer>[] gCat,
                            int[] state, int[][][] ans) {
    int m = state[0], c = state[1], t = state[2];
    int pt = t ^ 1;
    List<int[]> pre = new ArrayList<>();
    if (pt == 1) {
      for (int pc : gCat[c]) {
        if (ans[m][pc][1] == 0) {
          pre.add(new int[]{m, pc, pt});
        }
      }
    } else {
      for (int pm : gMouse[m]) {
        if (ans[pm][c][0] == 0) {
          pre.add(new int[]{pm, c, 0});
        }
      }
    }
    return pre;
  }
}

```

### CPP

```cpp
class Solution {
private:
  const int dirs[5] = {-1, 0, 1, 0, -1};
  int calc(vector<vector<int>> &gMouse, vector<vector<int>> &gCat,
           int mouseStart, int catStart, int hole) {
    int n = gMouse.size();
    vector<vector<vector<int>>> degree(n,
                                       vector<vector<int>>(n, vector<int>(2)));
    vector<vector<vector<int>>> ans(n, vector<vector<int>>(n, vector<int>(2)));
    queue<tuple<int, int, int>> q;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        degree[i][j][0] = gMouse[i].size();
        degree[i][j][1] = gCat[j].size();
      }
    }
    for (int i = 0; i < n; i++) {
      ans[hole][i][1] = 1;
      ans[i][hole][0] = 2;
      ans[i][i][1] = 2;
      ans[i][i][0] = 2;
      q.push(make_tuple(hole, i, 1));
      q.push(make_tuple(i, hole, 0));
      q.push(make_tuple(i, i, 0));
      q.push(make_tuple(i, i, 1));
    }
    while (!q.empty()) {
      auto state = q.front();
      q.pop();
      int m = get<0>(state), c = get<1>(state), t = get<2>(state);
      int result = ans[m][c][t];
      for (auto &prevState : getPrevStates(gMouse, gCat, state, ans)) {
        int pm = get<0>(prevState), pc = get<1>(prevState),
            pt = get<2>(prevState);
        if (pt == result - 1) {
          ans[pm][pc][pt] = result;
          q.push(prevState);
        } else {
          degree[pm][pc][pt]--;
          if (degree[pm][pc][pt] == 0) {
            ans[pm][pc][pt] = result;
            q.push(prevState);
          }
        }
      }
    }
    return ans[mouseStart][catStart][0];
  }
  vector<tuple<int, int, int>> getPrevStates(vector<vector<int>> &gMouse,
                                             vector<vector<int>> &gCat,
                                             tuple<int, int, int> &state,
                                             vector<vector<vector<int>>> &ans) {
    int m = get<0>(state), c = get<1>(state), t = get<2>(state);
    int pt = t ^ 1;
    vector<tuple<int, int, int>> pre;
    if (pt == 1) {
      for (int pc : gCat[c]) {
        if (ans[m][pc][1] == 0) {
          pre.push_back(make_tuple(m, pc, pt));
        }
      }
    } else {
      for (int pm : gMouse[m]) {
        if (ans[pm][c][0] == 0) {
          pre.push_back(make_tuple(pm, c, 0));
        }
      }
    }
    return pre;
  }

public:
  bool canMouseWin(vector<string> &grid, int catJump, int mouseJump) {
    int m = grid.size();
    int n = grid[0].length();
    int catStart = 0, mouseStart = 0, food = 0;
    vector<vector<int>> gMouse(m * n);
    vector<vector<int>> gCat(m * n);
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        char c = grid[i][j];
        if (c == '#') {
          continue;
        }
        int v = i * n + j;
        if (c == 'C') {
          catStart = v;
        } else if (c == 'M') {
          mouseStart = v;
        } else if (c == 'F') {
          food = v;
        }
        for (int d = 0; d < 4; ++d) {
          for (int k = 0; k <= mouseJump; k++) {
            int x = i + k * dirs[d];
            int y = j + k * dirs[d + 1];
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
              break;
            }
            gMouse[v].push_back(x * n + y);
          }
          for (int k = 0; k <= catJump; k++) {
            int x = i + k * dirs[d];
            int y = j + k * dirs[d + 1];
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
              break;
            }
            gCat[v].push_back(x * n + y);
          }
        }
      }
    }
    return calc(gMouse, gCat, mouseStart, catStart, food) == 1;
  }
};

```

### Python

```python
class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool: dirs = [0, 1, 0, - 1, 0] m = len(grid) n = len(grid[0]) nFloors = 0 cat = 0  # cat's position mouse = 0 # mouse's position def hash ( i : int , j : int ) -> int : return i * n + j for i in range ( m ): for j in range ( n ): if grid [ i ][ j ] != "#" : nFloors += 1 if grid [ i ][ j ] == "C" : cat = hash ( i , j ) elif grid [ i ][ j ] == "M" : mouse = hash ( i , j ) # dp(i, j, k) := True if mouse can win w// # Cat on (i // 8, i % 8), mouse on (j // 8, j % 8), and turns = k @ functools . lru_cache ( None ) def dp ( cat : int , mouse : int , turn : int ) -> bool : # We already search whole touchable grid if turn == nFloors * 2 : return False if turn % 2 == 0 : # mouse's turn i = mouse // n j = mouse % n for k in range ( 4 ): for jump in range ( mouseJump + 1 ): x = i + dirs [ k ] * jump y = j + dirs [ k + 1 ] * jump if x < 0 or x == m or y < 0 or y == n : break if grid [ x ][ y ] == "#" : break if grid [ x ][ y ] == "F" : # Mouse eats the food, so mouse win return True if dp ( cat , hash ( x , y ), turn + 1 ): return True # Mouse can't win, so mouse lose return False else : # cat's turn i = cat // n j = cat % n for k in range ( 4 ): for jump in range ( catJump + 1 ): x = i + dirs [ k ] * jump y = j + dirs [ k + 1 ] * jump if x < 0 or x == m or y < 0 or y == n : break if grid [ x ][ y ] == "#" : break if grid [ x ][ y ] == "F" : # Cat eats the food, so mouse lose return False nextCat = hash ( x , y ) if nextCat == mouse : # Cat catches mouse, so mouse lose return False if not dp ( nextCat , mouse , turn + 1 ): return False # Cat can't win, so mouse win return True return dp ( cat , mouse , 0 )

```