874. Walking Robot Simulation
Difficulty: Medium
Topics: Array
, Hash Table
, 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 left90
degrees. -
-1:
Turn right90
degrees. -
1 <= k <= 9:
Move forwardk
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):
- Move north 4 units to (0, 4).
- Turn right.
- 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):
- Move north 4 units to (0, 4).
- Turn right.
- Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
- Turn left.
- 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):
- Move north 6 units to (0, 6).
- Turn right.
- Turn right.
- 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
Solution:
We need to simulate the robot's movement on an infinite 2D grid based on a sequence of commands and avoid obstacles if any. The goal is to determine the maximum Euclidean distance squared that the robot reaches from the origin.
Approach
-
Direction Handling:
- The robot can face one of four directions: North, East, South, and West.
- We can represent these directions as vectors:
- North:
(0, 1)
- East:
(1, 0)
- South:
(0, -1)
- West:
(-1, 0)
- North:
-
Turning:
- A left turn
(-2)
will shift the direction counterclockwise by 90 degrees. - A right turn
(-1)
will shift the direction clockwise by 90 degrees.
- A left turn
-
Movement:
- For each move command, the robot will move in its current direction, one unit at a time. If it encounters an obstacle, it stops moving for that command.
-
Tracking Obstacles:
- Convert the obstacles list into a set of tuples for quick lookup, allowing the robot to quickly determine if it will hit an obstacle.
-
Distance Calculation:
- Track the maximum distance squared from the origin that the robot reaches during its movements.
Let's implement this solution in PHP: 874. Walking Robot Simulation
<?php
/**
* @param Integer[] $commands
* @param Integer[][] $obstacles
* @return Integer
*/
function robotSim($commands, $obstacles) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
echo robotSim([4,-1,3], []) . "\n"; // Output: 25
echo robotSim([4,-1,4,-2,4], [[2,4]]) . "\n"; // Output: 65
echo robotSim([6,-1,-1,6], []) . "\n"; // Output: 36
?>
Explanation:
- Direction Management: We use a list of vectors to represent the directions, allowing easy calculation of the next position after moving.
- Obstacle Detection: By storing obstacles in a set, we achieve O(1) time complexity for checking if a position is blocked by an obstacle.
- Distance Calculation: We continuously update the maximum squared distance the robot reaches as it moves.
Test Cases
- The example test cases provided are used to validate the solution:
-
[4,-1,3]
with no obstacles should return25
. -
[4,-1,4,-2,4]
with obstacles[[2,4]]
should return65
. -
[6,-1,-1,6]
with no obstacles should return36
.
-
This solution efficiently handles the problem constraints and calculates the maximum distance squared as required.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ๐. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)