Walking Robot Simulation

Leetcode Problem:

• Walking Robot Simulation

Summary

• Find the maximum squared Euclidean distance that a robot can reach in a grid while avoiding obstacles.

Approach

• This solution uses a set to store the positions of obstacles and a loop to iterate through the robot's commands
• It also uses arrays to represent the possible directions (north, east, south, west) and the current position of the robot
• The solution updates the current position of the robot and calculates the maximum squared Euclidean distance at each step.

Complexity

• O(n), where n is the number of commands.

Explain

• The solution starts by initializing a set to store the positions of obstacles and a variable to store the maximum squared Euclidean distance
• It then iterates through the robot's commands, updating the current position of the robot and calculating the maximum squared Euclidean distance at each step
• If the robot encounters an obstacle, it skips the current command and continues to the next one
• The solution returns the maximum squared Euclidean distance reached by the robot.

Solution Code:

class Solution {
public:
    set> s;
    int robotSim(vector& commands, vector>& obstacles) {
        int ans = 0;
        for(int i = 0 ; i < obstacles.size(); i++){
            int x = obstacles[i][0];
            int y = obstacles[i][1];
            s.insert({y, x});
        }
        int dir = 0;
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        int y = 0;
        int x = 0;
        for(int i = 0 ; i < commands.size(); i++){
            if(commands[i] == -1){
                dir = (dir + 1) %4;
                continue;
            } else if(commands[i] == -2){
                dir = (dir + 3) %4;
                continue;
            } 
            for(int j = 0 ; j < commands[i]; j++){
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny < -30000 || ny > 30000 || nx < -30000 || nx > 30000) continue;
                if (s.find({ny, nx}) != s.end()){
                    continue;
                }

                y = ny;
                x = nx;
                ans = max(ans, (y*y) + (x * x));
            }
        }
        return ans;
        
    }
};