874. 模拟行走机器人

[buuing]

机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：

• -2：向左转 90 度
• -1`：向右转 90 度
• 1 <= x <= 9：向前移动 x 个单位长度 在网格上有一些格子被视为障碍物。

第 i 个障碍物位于网格点 (obstacles[i][0], obstacles[i][1])

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。

返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。

示例 1：

输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)

示例 2：

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处

提示：

1. 0 <= commands.length <= 10000
2. 0 <= obstacles.length <= 10000
3. -30000 <= obstacle[i][0] <= 30000
4. -30000 <= obstacle[i][1] <= 30000
5. 答案保证小于 2 ^ 31

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/walking-robot-simulation 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 贪心算法

没啥, 就是模拟行走, 除此之外要注意的是, 题目要求的是最大欧式距离的平方, 而不是最终

const robotSim = (commands, obstacles) => {
  let direction = 10000, x = 0, y = 0
  let xMap = {}, yMap = {}, max = 0
  const findSmallestNumber = (start, end, set, flag) => {
    if (!set) return end
    while (start - end) {
      start += flag
      if (set.has(start)) {
        return start - flag
      }
    }
    return end
  }
  for (let obstacle of obstacles) {
    let [x, y] = obstacle
    if (xMap[x]) xMap[x].add(y)
    else xMap[x] = new Set([y])
    if (yMap[y]) yMap[y].add(x)
    else yMap[y] = new Set([x])
  }
  for (let curr of commands) {
    if (curr === -2) direction -= 1
    else if (curr === -1) direction += 1
    else {
      switch (direction % 4) {
        case 0:
          y = findSmallestNumber(y, y + curr, xMap[x], 1)
          break
        case 1:
          x = findSmallestNumber(x, x + curr, yMap[y], 1)
          break
        case 2:
          y = findSmallestNumber(y, y - curr, xMap[x], -1)
          break
        case 3:
          x = findSmallestNumber(x, x - curr, yMap[y], -1)
          break
      }
      max = Math.max(x ** 2 + y ** 2, max)
    }
  }
  return max
}