1728-cat-and-mouse-ii.js

/**
 * @param {string[]} grid
 * @param {number} catJump
 * @param {number} mouseJump
 * @return {boolean}
 */
const canMouseWin = function(grid, catJump, mouseJump) {
  let n,m,k,lim,cache,mpos = -1, cpos = -1, fpos = -1
  n = grid.length
  m = grid[0].length
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < m; j++) {
      if(grid[i][j] === 'M') mpos = i * m + j
      else if(grid[i][j] === 'C') cpos = i * m + j
      else if(grid[i][j] === 'F') fpos = i * m + j
    }
  }
  mnei = Array(n * m), cnei = Array(n * m)
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < m; j++) {
      mnei[i * m + j] = traj(i, j, mouseJump)
    }
  }
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < m; j++) {
      cnei[i * m + j] = traj(i, j, catJump)
    }
  }
  k = m * n
  lim = 100
  cache = Array.from({ length: lim }, () => Array(k * k).fill(0))

  for(let i = 0; i < lim; i++) {
    for(let j = 0; j < k * k; j++) {
      cache[i][j] = -1
    }
  }

  return mouseWin(mpos, cpos, 0)

  function traj(i, j, d) {
    if(grid[i][j] === '#') return []
    let pos = i * m + j
    let change = []
    change.push(pos)
    for(let k = 1; k < d + 1; k++) {
      if(i + k >= n || grid[i + k][j] === '#') break
      change.push(pos + k * m)
    }
    for(let k = 1; k < d + 1; k++) {
      if(i - k < 0 || grid[i - k][j] === '#') break
      change.push(pos - k * m) 
    }
    for(let k = 1; k < d + 1; k++) {
      if(j + k >= m || grid[i][j + k] === '#') break
      change.push(pos + k)
    }
    for(let k = 1; k < d + 1; k++) {
      if(j - k < 0 || grid[i][j - k] === '#') break
      change.push(pos - k)
    }
    return change
  }
  
  function mouseWin(mpos, cpos, turn) {
    if(turn === lim) return false
    let e = mpos * k + cpos
    if(cache[turn][e] >= 0) return cache[turn][e] === 1
    if(cpos === fpos || cpos === mpos) return false
    if(mpos === fpos) return true
    if((turn & 1) !== 0) {
      let b = 0
      for(let newCpos of cnei[cpos]) {
        if(!mouseWin(mpos, newCpos, turn + 1)) b = 1
      }
      if(b===0) cache[turn][e] = 1
      else cache[turn][e] = 0
    } else {
      let b = 0
      for(let newMpos of mnei[mpos]) {
        if(mouseWin(newMpos, cpos, turn + 1)) b = 1
      }
      if(b === 1) cache[turn][e] = 1
      else cache[turn][e] = 0
    }
    return cache[turn][e] === 1
  }
};