1728. Cat and Mouse II

Description

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:

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:

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O((mn)³*(m+n))
• Space complexity: O((mn)³)

 

JavaScript

/**
 * @param {string[]} grid
 * @param {number} catJump
 * @param {number} mouseJump
 * @return {boolean}
 */
const canMouseWin = function (grid, catJump, mouseJump) {
  const m = grid.length;
  const n = grid[0].length;
  const mouse = { row: 0, col: 0 };
  const cat = { row: 0, col: 0 };
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const memo = new Map();
  let floors = 0;

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = grid[row][col];

      if (value !== '#') floors += 1;
      if (value === 'M') {
        mouse.row = row;
        mouse.col = col;
      } else if (value === 'C') {
        cat.row = row;
        cat.col = col;
      }
    }
  }

  const isMouseWin = (mouseRow, mouseCol, catRow, catCol, turns) => {
    if (turns >= floors * 2) return false;
    const key = `${mouseRow},${mouseCol},${catRow},${catCol},${turns}`;

    if (memo.has(key)) return memo.get(key);
    const round = turns % 2 ? 'C' : 'M';
    const mouseRound = round === 'M';
    const jump = mouseRound ? mouseJump : catJump;

    for (const [row, col] of directions) {
      for (let move = 0; move <= jump; move++) {
        const moveRow = row * move;
        const moveCol = col * move;
        const nextRow = (mouseRound ? mouseRow : catRow) + moveRow;
        const nextCol = (mouseRound ? mouseCol : catCol) + moveCol;

        if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) break;
        const value = grid[nextRow][nextCol];

        if (value === '#') break;
        if (value === 'F') {
          memo.set(key, mouseRound);

          return mouseRound;
        }

        if (mouseRound && isMouseWin(nextRow, nextCol, catRow, catCol, turns + 1)) {
          memo.set(key, true);

          return true;
        }

        if (!mouseRound) {
          if (mouseRow === nextRow && mouseCol === nextCol) {
            memo.set(key, false);

            return false;
          }

          if (!isMouseWin(mouseRow, mouseCol, nextRow, nextCol, turns + 1)) {
            memo.set(key, false);

            return false;
          }
        }
      }
    }

    memo.set(key, !mouseRound);

    return !mouseRound;
  };

  return isMouseWin(mouse.row, mouse.col, cat.row, cat.col, 0);
};