874. Walking Robot Simulation

A robot on an infinite XY-plane starts at point `(0, 0)` and faces north. The robot can receive one of three possible types of `commands`:

• `-2`: turn left `90` degrees,
• `-1`: turn right `90` degrees, or
• `1 <= k <= 9`: move forward `k` units.

Some of the grid squares are `obstacles`. The `ith` obstacle is at grid point `obstacles[i] = (xi, yi)`.

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the maximum Euclidean distance that the robot will be 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.

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 away from the origin is (3, 4), which 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 away from the origin is (1, 8), which is 12 + 82 = 65 units away.
```

Constraints:

• `1 <= commands.length <= 104`
• `commands[i]` is one of the values in the list `[-2,-1,1,2,3,4,5,6,7,8,9]`.
• `0 <= obstacles.length <= 104`
• `-3 * 104 <= xi, yi <= 3 * 104`
• The answer is guaranteed to be less than `231`.

874. Walking Robot Simulation
``````struct Solution;

#[derive(Debug, PartialEq, Eq, Hash, Default)]
struct Point {
x: i32,
y: i32,
}

impl Point {
fn new(x: i32, y: i32) -> Self {
Point { x, y }
}
fn from(v: Vec<i32>) -> Self {
Point { x: v[0], y: v[1] }
}
fn square_distance(&self) -> i32 {
self.x * self.x + self.y * self.y
}
}

#[derive(Default)]
struct Robot {
position: Point,
direction: usize,
}

impl Robot {
fn new() -> Self {
Robot {
position: Point { x: 0, y: 0 },
direction: 0,
}
}
fn left(&mut self) {
self.direction = (self.direction + 1) % 4;
}
fn right(&mut self) {
self.direction = (self.direction + 3) % 4;
}
fn next(&self) -> Point {
let x = self.position.x;
let y = self.position.y;
match self.direction {
0 => Point::new(x, y + 1),
1 => Point::new(x - 1, y),
2 => Point::new(x, y - 1),
3 => Point::new(x + 1, y),
_ => unreachable!(),
}
}
fn walk(&mut self, step: usize, grid: &Grid) {
let mut i = 0;
while i < step && !grid.obstacles.contains(&self.next()) {
self.position = self.next();
i += 1;
}
}
}

use std::collections::HashSet;

struct Grid {
obstacles: HashSet<Point>,
}

impl Grid {
fn new(obstacles: Vec<Point>) -> Self {
let mut hs: HashSet<Point> = HashSet::new();
for x in obstacles {
hs.insert(x);
}
Grid { obstacles: hs }
}
}

impl Solution {
fn robot_sim(commands: Vec<i32>, obstacles: Vec<Vec<i32>>) -> i32 {
let grid: Grid = Grid::new(obstacles.iter().map(|v| Point::new(v[0], v[1])).collect());
let mut robot = Robot::new();
let mut max = 0;
for command in commands {
match command {
-2 => robot.left(),
-1 => robot.right(),
_ => {
robot.walk(command as usize, &grid);
max = i32::max(robot.position.square_distance(), max);
}
}
}
max as i32
}
}

#[test]
fn test() {
let commands: Vec<i32> = vec![4, -1, 3];
let obstacles: Vec<Vec<i32>> = vec![];
assert_eq!(Solution::robot_sim(commands, obstacles), 25);
let commands: Vec<i32> = vec![4, -1, 4, -2, 4];
let obstacles: Vec<Vec<i32>> = vec![vec![2, 4]];
assert_eq!(Solution::robot_sim(commands, obstacles), 65);
}
``````