Question

874. Walking Robot Simulation

中文文档

Description

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands:

• -2: Turn left 90 degrees.
• -1: Turn right 90 degrees.
• 1 <= k <= 9: Move forward k units, one unit at a time.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command.

Return _the maximum Euclidean distance that the robot ever gets from the origin squared (i.e. if the distance is _5_, return _25_)_.

Note:

• North means +Y direction.
• East means +X direction.
• South means -Y direction.
• West means -X direction.
• There can be obstacle in [0,0].

 

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 3 units to (3, 4).
The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
4. Turn left.
5. Move north 4 units to (1, 8).
The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.

Example 3:

Input: commands = [6,-1,-1,6], obstacles = []
Output: 36
Explanation: The robot starts at (0, 0):
1. Move north 6 units to (0, 6).
2. Turn right.
3. Turn right.
4. Move south 6 units to (0, 0).
The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.

 

Constraints:

• 1 <= commands.length <= 104
• commands[i] is either -2, -1, or an integer in the range [1, 9].
• 0 <= obstacles.length <= 104
• -3 * 104 <= xi, yi <= 3 * 104
• The answer is guaranteed to be less than 231.

Solutions

Solution 1: Hash table + simulation

We define a direction array $dirs=[0, 1, 0, -1, 0]$ of length $5$, where adjacent elements in the array represent a direction. That is, $(dirs[0], dirs[1])$ represents north, and $(dirs[1], dirs[2])$ represents east, and so on.

We use a hash table $s$ to store the coordinates of all obstacles, so that we can determine in $O(1)$ time whether the next step will encounter an obstacle.

We use two variables $x$ and $y$ to represent the current coordinates of the robot, initially $x = y = 0$. The variable $k$ represents the current direction of the robot, and the answer variable $ans$ represents the maximum Euclidean distance squared of the robot from the origin.

Next, we traverse each element $c$ in the array $commands$:

• If $c = -2$, it means that the robot turns left by $90$ degrees, that is, $k = (k + 3) \bmod 4$;
• If $c = -1$, it means that the robot turns right by $90$ degrees, that is, $k = (k + 1) \bmod 4$;
• Otherwise, it means that the robot moves forward by $c$ units of length. We combine the robot's current direction $k$ with the direction array $dirs$, and we can get the increment of the robot on the $x$ axis and the $y$ axis. We add the increment of $c$ units of length to $x$ and $y$ respectively, and judge whether the new coordinates $(x, y)$ after each move are in the coordinates of obstacles. If not, update the answer $ans$, otherwise stop simulating and perform the simulation of the next instruction.

Finally return the answer $ans$.

Time complexity is $O(C \times n + m)$, space complexity is $O(m)$. Where $C$ represents the maximum number of steps that can be moved each time, and $n$ and $m$ respectively represent the lengths of arrays $commands$ and arrays $obstacles$.

class Solution:
  def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
    dirs = (0, 1, 0, -1, 0)
    s = {(x, y) for x, y in obstacles}
    ans = k = 0
    x = y = 0
    for c in commands:
      if c == -2:
        k = (k + 3) % 4
      elif c == -1:
        k = (k + 1) % 4
      else:
        for _ in range(c):
          nx, ny = x + dirs[k], y + dirs[k + 1]
          if (nx, ny) in s:
            break
          x, y = nx, ny
          ans = max(ans, x * x + y * y)
    return ans

class Solution {
  public int robotSim(int[] commands, int[][] obstacles) {
    int[] dirs = {0, 1, 0, -1, 0};
    Set<Integer> s = new HashSet<>(obstacles.length);
    for (var e : obstacles) {
      s.add(f(e[0], e[1]));
    }
    int ans = 0, k = 0;
    int x = 0, y = 0;
    for (int c : commands) {
      if (c == -2) {
        k = (k + 3) % 4;
      } else if (c == -1) {
        k = (k + 1) % 4;
      } else {
        while (c-- > 0) {
          int nx = x + dirs[k], ny = y + dirs[k + 1];
          if (s.contains(f(nx, ny))) {
            break;
          }
          x = nx;
          y = ny;
          ans = Math.max(ans, x * x + y * y);
        }
      }
    }
    return ans;
  }

  private int f(int x, int y) {
    return x * 60010 + y;
  }
}

class Solution {
public:
  int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
    int dirs[5] = {0, 1, 0, -1, 0};
    auto f = [](int x, int y) {
      return x * 60010 + y;
    };
    unordered_set<int> s;
    for (auto& e : obstacles) {
      s.insert(f(e[0], e[1]));
    }
    int ans = 0, k = 0;
    int x = 0, y = 0;
    for (int c : commands) {
      if (c == -2) {
        k = (k + 3) % 4;
      } else if (c == -1) {
        k = (k + 1) % 4;
      } else {
        while (c--) {
          int nx = x + dirs[k], ny = y + dirs[k + 1];
          if (s.count(f(nx, ny))) {
            break;
          }
          x = nx;
          y = ny;
          ans = max(ans, x * x + y * y);
        }
      }
    }
    return ans;
  }
};

func robotSim(commands []int, obstacles [][]int) (ans int) {
  dirs := [5]int{0, 1, 0, -1, 0}
  type pair struct{ x, y int }
  s := map[pair]bool{}
  for _, e := range obstacles {
    s[pair{e[0], e[1]}] = true
  }
  var x, y, k int
  for _, c := range commands {
    if c == -2 {
      k = (k + 3) % 4
    } else if c == -1 {
      k = (k + 1) % 4
    } else {
      for ; c > 0 && !s[pair{x + dirs[k], y + dirs[k+1]}]; c-- {
        x += dirs[k]
        y += dirs[k+1]
        ans = max(ans, x*x+y*y)
      }
    }
  }
  return
}

function robotSim(commands: number[], obstacles: number[][]): number {
  const dirs = [0, 1, 0, -1, 0];
  const s: Set<number> = new Set();
  const f = (x: number, y: number) => x * 60010 + y;
  for (const [x, y] of obstacles) {
    s.add(f(x, y));
  }
  let [ans, x, y, k] = [0, 0, 0, 0];
  for (let c of commands) {
    if (c === -2) {
      k = (k + 3) % 4;
    } else if (c === -1) {
      k = (k + 1) % 4;
    } else {
      while (c-- > 0) {
        const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
        if (s.has(f(nx, ny))) {
          break;
        }
        [x, y] = [nx, ny];
        ans = Math.max(ans, x * x + y * y);
      }
    }
  }
  return ans;
}