In this guide, you will get 874. Walking Robot Simulation LeetCode Solution with the best time and space complexity. The solution to Walking Robot Simulation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot receives an array of integers commands, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:
-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, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.
Return the maximum squared Euclidean distance that the robot reaches at any point in its path (i.e. if the distance is 5, return 25).
Note:
There can be an obstacle at (0, 0). If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to (0, 0) due to the obstacle.
North means +Y direction.
East means +X direction.
South means -Y direction.
West means -X direction.
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 = [[0,0]]
Output: 36
Explanation:
The robot starts at (0, 0):
Move north 6 units to (0, 6).
Turn right.
Turn right.
Move south 5 units and get blocked by the obstacle at (0,0), robot is at (0, 1).
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.
874. Walking Robot Simulation LeetCode Solution in C++
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int ans = 0;
int d = 0; // 0 := north, 1 := east, 2 := south, 3 := west
int x = 0; // the start x
int y = 0; // the start y
unordered_set<pair<int, int>, PairHash> obstaclesSet;
for (const vector<int>& obstacle : obstacles) {
const int x = obstacle[0];
const int y = obstacle[1];
obstaclesSet.insert({x, y});
}
for (const int command : commands) {
if (command == -1) {
d = (d + 1) % 4;
} else if (command == -2) {
d = (d + 3) % 4;
} else {
for (int step = 0; step < command; ++step) {
if (obstaclesSet.contains({x + dirs[d][0], y + dirs[d][1]}))
break;
x += dirs[d][0];
y += dirs[d][1];
}
}
ans = max(ans, x * x + y * y);
}
return ans;
}
private:
struct PairHash {
size_t operator()(const pair<int, int>& p) const {
return p.first ^ p.second;
}
};
}; /* code provided by PROGIEZ */
874. Walking Robot Simulation LeetCode Solution in Java
class Solution {
public int robotSim(int[] commands, int[][] obstacles) {
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int ans = 0;
int d = 0; // 0 := north, 1 := east, 2 := south, 3 := west
int x = 0; // the start x
int y = 0; // the start y
Set<Pair<Integer, Integer>> obstaclesSet = new HashSet<>();
for (int[] obstacle : obstacles) {
final int x_ = obstacle[0];
final int y_ = obstacle[1];
obstaclesSet.add(new Pair<>(x_, y_));
}
for (final int command : commands) {
if (command == -1) {
d = (d + 1) % 4;
} else if (command == -2) {
d = (d + 3) % 4;
} else {
for (int step = 0; step < command; ++step) {
if (obstaclesSet.contains(new Pair<>(x + dirs[d][0], y + dirs[d][1])))
break;
x += dirs[d][0];
y += dirs[d][1];
}
}
ans = Math.max(ans, x * x + y * y);
}
return ans;
}
} // code provided by PROGIEZ
874. Walking Robot Simulation LeetCode Solution in Python
class Solution:
def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
ans = 0
d = 0 # 0 := north, 1 := east, 2 := south, 3 := west
x = 0 # the start x
y = 0 # the start y
obstaclesSet = {(x, y) for x, y in obstacles}
for command in commands:
if command == -1:
d = (d + 1) % 4
elif command == -2:
d = (d + 3) % 4
else:
for _ in range(command):
if (x + dirs[d][0], y + dirs[d][1]) in obstaclesSet:
break
x += dirs[d][0]
y += dirs[d][1]
ans = max(ans, x * x + y * y)
return ans # code by PROGIEZ
