# 1728. Cat and Mouse II          • Time: $O(m^3n^3 \cdot (m + n))$
• Space: $O(m^3n^3)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 class Solution { public: bool canMouseWin(vector& grid, int catJump, int mouseJump) { m = grid.size(); n = grid.size(); int cat; // cat's position int mouse; // mouse's position for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (grid[i][j] != '#') ++nFloors; if (grid[i][j] == 'C') cat = hash(i, j); else if (grid[i][j] == 'M') mouse = hash(i, j); } // dp[i][j][k] := true if the mouse can win, where the cat is on // (i / 8, i % 8), the mouse is on (j / 8, j % 8), and the turns = k dp.resize(m * n, vector>(m * n, vector(nFloors * 2, -1))); return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump); } private: const vector dirs{0, 1, 0, -1, 0}; int m; int n; int nFloors = 0; vector>> dp; bool canMouseWin(const vector& grid, int cat, int mouse, int turn, const int& catJump, const int& mouseJump) { // We already search the whole touchable grid. if (turn == nFloors * 2) return false; if (dp[cat][mouse][turn] != -1) return dp[cat][mouse][turn]; if (turn % 2 == 0) { // the mouse's turn const int i = mouse / n; const int j = mouse % n; for (int k = 0; k < 4; ++k) { for (int jump = 0; jump <= mouseJump; ++jump) { const int x = i + dirs[k] * jump; const int y = j + dirs[k + 1] * jump; if (x < 0 || x == m || y < 0 || y == n) break; if (grid[x][y] == '#') break; // The mouse eats the food, so the mouse wins. if (grid[x][y] == 'F') return dp[cat][mouse][turn] = true; if (canMouseWin(grid, cat, hash(x, y), turn + 1, catJump, mouseJump)) return dp[cat][mouse][turn] = true; } } // The mouse can't win, so the mouse loses. return dp[cat][mouse][turn] = false; } else { // the cat's turn const int i = cat / n; const int j = cat % n; for (int k = 0; k < 4; ++k) { for (int jump = 0; jump <= catJump; ++jump) { const int x = i + dirs[k] * jump; const int y = j + dirs[k + 1] * jump; if (x < 0 || x == m || y < 0 || y == n) break; if (grid[x][y] == '#') break; // The cat eats the food, so the mouse loses. if (grid[x][y] == 'F') return dp[cat][mouse][turn] = false; const int nextCat = hash(x, y); // The cat catches the mouse, so the mouse loses. if (nextCat == mouse) return dp[cat][mouse][turn] = false; if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump)) return dp[cat][mouse][turn] = false; } } // The cat can't win, so the mouse wins. return dp[cat][mouse][turn] = true; } } int hash(int i, int j) { return i * n + j; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 class Solution { public boolean canMouseWin(String[] grid, int catJump, int mouseJump) { m = grid.length; n = grid.length(); int cat = 0; // cat's position int mouse = 0; // mouse's position for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (grid[i].charAt(j) != '#') ++nFloors; if (grid[i].charAt(j) == 'C') cat = hash(i, j); else if (grid[i].charAt(j) == 'M') mouse = hash(i, j); } // dp[i][j][k] := true if the mouse can win, where the cat is on // (i / 8, i % 8), the mouse is on (j / 8, j % 8), and the turns = k dp = new Boolean[m * n][m * n][nFloors * 2]; return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump); } private static final int[] dirs = {0, 1, 0, -1, 0}; private int m; private int n; private int nFloors = 0; private Boolean[][][] dp; private boolean canMouseWin(final String[] grid, int cat, int mouse, int turn, int catJump, int mouseJump) { // We already search the whole touchable grid. if (turn == nFloors * 2) return false; if (dp[cat][mouse][turn] != null) return dp[cat][mouse][turn]; if (turn % 2 == 0) { // the mouse's turn final int i = mouse / n; final int j = mouse % n; for (int k = 0; k < 4; ++k) { for (int jump = 0; jump <= mouseJump; ++jump) { final int x = i + dirs[k] * jump; final int y = j + dirs[k + 1] * jump; if (x < 0 || x == m || y < 0 || y == n) break; if (grid[x].charAt(y) == '#') break; // The mouse eats the food, so the mouse wins. if (grid[x].charAt(y) == 'F') return dp[cat][mouse][turn] = true; if (canMouseWin(grid, cat, hash(x, y), turn + 1, catJump, mouseJump)) return dp[cat][mouse][turn] = true; } } // The mouse can't win, so the mouse loses. return dp[cat][mouse][turn] = false; } else { // the cat's turn final int i = cat / n; final int j = cat % n; for (int k = 0; k < 4; ++k) { for (int jump = 0; jump <= catJump; ++jump) { final int x = i + dirs[k] * jump; final int y = j + dirs[k + 1] * jump; if (x < 0 || x == m || y < 0 || y == n) break; if (grid[x].charAt(y) == '#') break; // The cat eats the food, so the mouse loses. if (grid[x].charAt(y) == 'F') return dp[cat][mouse][turn] = false; final int nextCat = hash(x, y); if (nextCat == mouse) // The cat catches the mouse, so the mouse loses. return dp[cat][mouse][turn] = false; if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump)) return dp[cat][mouse][turn] = false; } } // The cat can't win, so the mouse wins. return dp[cat][mouse][turn] = true; } } private int hash(int i, int j) { return i * n + j; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 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) 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) @functools.lru_cache(None) def dp(cat: int, mouse: int, turn: int) -> bool: """ Returns True if the mouse can win, where the cat is on (i / 8, i % 8), the mouse is on (j / 8, j % 8), and the turns = k. """ # We already search the whole touchable grid. if turn == nFloors * 2: return False if turn % 2 == 0: # the 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 # The mouse eats the food, so the mouse wins. if grid[x][y] == 'F': return True if dp(cat, hash(x, y), turn + 1): return True # The mouse can't win, so the mouse loses. return False else: # the 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 # The cat eats the food, so the mouse loses. if grid[x][y] == 'F': return False nextCat = hash(x, y) # The cat catches the mouse, so the mouse loses. if nextCat == mouse: return False if not dp(nextCat, mouse, turn + 1): return False # The cat can't win, so the mouse wins. return True return dp(cat, mouse, 0)