LeetCode每日一题(874. Walking Robot Simulation)

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.

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.

---

开始想用二分搜索找路上的障碍， 结果怎么都整不出来， 最后又审了一遍题， 发现步数范围是 1 到 9， 命令的数量小于 10 的 4 次方， 这样一算， 就算是一步一步的算， 也就是 10 的 5 次方的数量级， 是可以接受的。 这题我用了整数来代表方向(0 到 3), 实际的位移就可以直接计算得出了。

---

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn robot_sim(commands: Vec<i32>, obstacles: Vec<Vec<i32>>) -> i32 {
        let mut x = 0;
        let mut y = 0;
        let mut dir = 0;
        let obstacles = obstacles.into_iter().fold(HashMap::new(), |mut m, l| {
            m.entry(l[0]).or_insert(HashSet::new()).insert(l[1]);
            m
        });
        let mut ans = 0;
        for command in commands {
            match command {
                -2 => dir = (dir + 3) % 4,
                -1 => dir = (dir + 1) % 4,
                _ => {
                    if dir % 2 == 1 {
                        for _ in 0..command {
                            if let Some(obst) = obstacles.get(&(x - (dir - 2))) {
                                if obst.contains(&y) {
                                    break;
                                }
                            }
                            x -= dir - 2;
                        }
                        ans = ans.max(x.pow(2) + y.pow(2));
                    } else {
                        for _ in 0..command {
                            if let Some(obst) = obstacles.get(&x) {
                                if obst.contains(&(y - (dir - 1))) {
                                    break;
                                }
                            }
                            y -= dir - 1;
                        }
                        ans = ans.max(x.pow(2) + y.pow(2));
                    }
                }
            }
        }
        ans
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45