874.模拟行走机器人.md

874.模拟行走机器人

/*
 * @lc app=leetcode.cn id=874 lang=typescript
 *
 * [874] 模拟行走机器人
 */

// @lc code=start
function robotSim(commands: number[], obstacles: number[][]): number {}
// @lc code=end

解法 1:

function robotSim(commands: number[], obstacles: number[][]): number {
  const directions = [
    { dx: 0, dy: 1 }, // 上 // 北
    { dx: 1, dy: 0 }, // 右 // 东
    { dx: 0, dy: -1 }, // 下 // 南
    { dx: -1, dy: 0 }, // 左 // 西
  ]
  const obstacleCache: {
    x: { [key: number]: number[] }
    y: { [key: number]: number[] }
  } = { x: {}, y: {} }
  for (const [x, y] of obstacles) {
    obstacleCache.x[x] ? obstacleCache.x[x].push(y) : (obstacleCache.x[x] = [y])
    obstacleCache.y[y] ? obstacleCache.y[y].push(x) : (obstacleCache.y[y] = [x])
  }

  let dIndex = 0
  let point = { x: 0, y: 0 }
  let max = 0
  for (const command of commands) {
    if (command === -2) dIndex = (dIndex + 4 - 1) % 4
    else if (command === -1) dIndex = (dIndex + 1) % 4
    else {
      const { x, y } = point
      const { dx, dy } = directions[dIndex]

      let min = command
      if (dx !== 0) {
        const obstacles = obstacleCache.y[y] ?? []
        for (const obstacleX of obstacles) {
          ;(obstacleX - x) * dx > 0 && (min = Math.min(min, Math.abs(obstacleX - x) - 1))
        }
        point = { x: x + dx * min, y }
      } else {
        const obstacles = obstacleCache.x[x] ?? []
        for (const obstacleY of obstacles) {
          ;(obstacleY - y) * dy > 0 && (min = Math.min(min, Math.abs(obstacleY - y) - 1))
        }
        point = { x, y: y + dy * min }
      }

      max = Math.max(max, point.x ** 2 + point.y ** 2)
    }
  }
  return max
}

解法 2

function robotSim(commands: number[], obstacles: number[][]): number {
  const dir = { x: [0, 1, 0, -1], y: [1, 0, -1, 0] }

  const obstacleSet = new Set<string>(obstacles.map(([x, y]) => `${x},${y}`))

  let dIndex = 0
  let point = { x: 0, y: 0 }
  let max = 0
  for (let command of commands) {
    if (command === -2) dIndex = (dIndex + 3) % 4
    else if (command === -1) dIndex = (dIndex + 1) % 4
    else {
      const { x, y } = point
      const [dx, dy] = [dir.x[dIndex], dir.y[dIndex]]
      let dis = 1 // 移动的距离
      while (dis <= command) {
        if (obstacleSet.has(`${x + dis * dx},${y + dis * dy}`)) break
        point = { x: x + dis * dx, y: y + dis * dy }
        dis++
      }

      max = Math.max(max, point.x ** 2 + point.y ** 2)
    }
  }
  return max
}

Case

test.each([
  { commands: [4, -1, 3], obstacles: [], result: 25 },
  { commands: [4, -1, 4, -2, 4], obstacles: [[2, 4]], result: 65 },
  { commands: [6, -1, -1, 6], obstacles: [], result: 36 },
  {
    commands: [-2, 8, 3, 7, -1],
    obstacles: [
      [-4, -1],
      [1, -1],
      [1, 4],
      [5, 0],
      [4, 5],
      [-2, -1],
      [2, -5],
      [5, 1],
      [-3, -1],
      [5, -3],
    ],
    result: 324,
  },
  {
    commands: [2, -1, 8, -1, 6],
    obstacles: [
      [1, 5],
      [-5, -5],
      [0, 4],
      [-1, -1],
      [4, 5],
      [-5, -3],
      [-2, 1],
      [-2, -5],
      [0, 5],
      [0, -1],
    ],
    result: 80,
  },
  {
    commands: [-2, -1, -2, 3, 7],
    obstacles: [
      [1, -3],
      [2, -3],
      [4, 0],
      [-2, 5],
      [-5, 2],
      [0, 0],
      [4, -4],
      [-2, -5],
      [-1, -2],
      [0, 2],
    ],
    result: 100,
  },
])('commands = $commands, obstacles = $obstacles', ({ commands, obstacles, result }) => {
  expect(robotSim(commands, obstacles)).toBe(result)
})