Add solution #1728

JoshCrozier · JoshCrozier · commit 5937b7c0be2a · 2025-04-27T15:15:25.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,504 LeetCode solutions in JavaScript
+# 1,505 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1332,6 +1332,7 @@
 1725|[Number Of Rectangles That Can Form The Largest Square](./solutions/1725-number-of-rectangles-that-can-form-the-largest-square.js)|Easy|
 1726|[Tuple with Same Product](./solutions/1726-tuple-with-same-product.js)|Medium|
 1727|[Largest Submatrix With Rearrangements](./solutions/1727-largest-submatrix-with-rearrangements.js)|Medium|
+1728|[Cat and Mouse II](./solutions/1728-cat-and-mouse-ii.js)|Hard|
 1732|[Find the Highest Altitude](./solutions/1732-find-the-highest-altitude.js)|Easy|
 1748|[Sum of Unique Elements](./solutions/1748-sum-of-unique-elements.js)|Easy|
 1749|[Maximum Absolute Sum of Any Subarray](./solutions/1749-maximum-absolute-sum-of-any-subarray.js)|Medium|
diff --git a/solutions/1728-cat-and-mouse-ii.js b/solutions/1728-cat-and-mouse-ii.js
@@ -0,0 +1,107 @@
+/**
+ * 1728. Cat and Mouse II
+ * https://leetcode.com/problems/cat-and-mouse-ii/
+ * Difficulty: Hard
+ *
+ * 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.
+ */
+
+/**
+ * @param {string[]} grid
+ * @param {number} catJump
+ * @param {number} mouseJump
+ * @return {boolean}
+ */
+var canMouseWin = function(grid, catJump, mouseJump) {
+  if (typeof grid === 'string') grid = [grid];
+  const rows = grid.length;
+  const cols = grid[0].length;
+  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
+  let mouse;
+  let cat;
+  let food;
+  let available = 0;
+
+  for (let i = 0; i < rows; i++) {
+    for (let j = 0; j < cols; j++) {
+      const cell = grid[i][j];
+      if (cell !== '#') available++;
+      if (cell === 'M') mouse = [i, j];
+      else if (cell === 'C') cat = [i, j];
+      else if (cell === 'F') food = [i, j];
+    }
+  }
+
+  const memo = new Map();
+
+  return canWin(0, mouse, cat);
+
+  function getKey(turn, [mr, mc], [cr, cc]) {
+    return `${turn},${mr},${mc},${cr},${cc}`;
+  }
+
+  function isValid(r, c) {
+    return r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] !== '#';
+  }
+
+  function canWin(turn, mousePos, catPos) {
+    if (turn >= available * 2) return false;
+
+    const key = getKey(turn, mousePos, catPos);
+    if (memo.has(key)) return memo.get(key);
+
+    const isMouseTurn = turn % 2 === 0;
+    const [r, c] = isMouseTurn ? mousePos : catPos;
+    const maxJump = isMouseTurn ? mouseJump : catJump;
+
+    for (const [dr, dc] of dirs) {
+      for (let jump = 0; jump <= maxJump; jump++) {
+        const nr = r + dr * jump;
+        const nc = c + dc * jump;
+        if (!isValid(nr, nc)) break;
+
+        if (isMouseTurn) {
+          if (grid[nr][nc] === 'F' || canWin(turn + 1, [nr, nc], catPos)) {
+            memo.set(key, true);
+            return true;
+          }
+        } else {
+          if (grid[nr][nc] === 'F' || (nr === mousePos[0] && nc === mousePos[1])
+              || !canWin(turn + 1, mousePos, [nr, nc])) {
+            memo.set(key, false);
+            return false;
+          }
+        }
+      }
+    }
+
+    memo.set(key, !isMouseTurn);
+    return !isMouseTurn;
+  }
+};
