Leetcode 2069: Walking Robot Simulation II
A robot is placed on a grid and initially faces East. It is instructed to move forward by a specified number of steps. If the robot attempts to move out of bounds, it turns 90 degrees counterclockwise and tries again. The task is to implement a class for the robot that can handle these movements and return its current position and direction.
Problem
Approach
Steps
Complexity
Input: The input consists of two parts: the dimensions of the grid and the instructions for the robot's movements. The robot starts at position (0, 0), facing East.
Example:
Constraints:
Output: The output includes the robot's current position in the grid (as a two-element array [x, y]) and its current facing direction.
Example:
Constraints:
Goal: To move the robot based on instructions and handle boundary conditions with turning.
Steps:
• Initialize the grid dimensions and robot's starting position and direction.
• Implement logic to move the robot one step at a time, checking for boundary conditions and turning the robot if necessary.
• Ensure that the robot's position and direction are correctly updated after each movement instruction.
Goal: The robot is constrained within a grid of width and height. At most 10^4 operations (steps, getPos, and getDir) can be performed.
Steps:
Assumptions:
• The grid's width and height will always be at least 2.
• The robot will always start at position (0, 0) and face East.
• Input: Robot robot = new Robot(6, 3);
• Explanation: Here, the robot is initialized on a 6x3 grid, starting at position (0, 0), facing East.
• Input: robot.step(2); robot.getPos(); robot.getDir();
• Explanation: The robot moves two steps East and is now at position (2, 0), facing East.
• Input: robot.step(2); robot.getPos(); robot.getDir();
• Explanation: After moving two more steps East, the robot is at position (4, 0), still facing East.
• Input: robot.step(2); robot.step(1); robot.step(4); robot.getPos(); robot.getDir();
• Explanation: After additional steps, the robot moves in different directions, including turning when hitting boundaries, eventually reaching position (1, 2) facing West.
Approach: The robot's movement can be tracked by updating its position and direction after each step, with a check for boundary conditions that triggers a 90-degree turn.
Observations:
• The robot's direction can be represented by an integer (0 = East, 1 = North, 2 = West, 3 = South).
• The robot's movement follows a simple grid structure, with checks for boundaries.
• We need to manage the robot's movement and turning behavior efficiently, especially given the constraint on the number of operations.
Steps:
• Initialize the grid and the robot at position (0, 0) facing East.
• Define the movement logic for each direction (East, North, West, South).
• Handle boundary conditions by turning the robot when it moves out of bounds.
• Use the modulo operator to optimize repeated steps and ensure the robot doesn't move unnecessarily far beyond the grid.
Empty Inputs:
• The grid must always have a valid size.
Large Inputs:
• For large step values, use modulo operations to prevent excessive calculations.
Special Values:
• Ensure that the robot turns properly when hitting boundaries.
Constraints:
• Ensure that the total number of operations doesn't exceed 10^4.
int w, h, i, j, dir, per;
Robot(int width, int height) {
w = width;
h = height;
i = 0;
j = 0;
dir = 0;
per = 2 * (w + h - 2);
}
void step(int num) {
if(num > per) {
num %= per;
if(i == 0 && j == 0 && dir == 0) dir = 3;
}
int mo[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while(num) {
int x = i + mo[dir][0], y = j + mo[dir][1];
if(x >= w || y >= h || x < 0 || y < 0) {
dir = (dir + 1) % 4;
} else {
i = x;
j = y;
num--;
}
}
}
vector<int> getPos() {
return {i, j};
}
string getDir() {
switch(dir) {
case 0: return "East" ; break;
case 1: return "North" ; break;
case 2: return "West" ; break;
case 3: return "South" ; break;
}
return "";
}
};
/**
* Your Robot object will be instantiated and called as such:
* Robot* obj = new Robot(width, height);
* obj->step(num);
* vector<int> param_2 = obj->getPos();
* string param_3 = obj->getDir();
1 : Variable Declaration
int w, h, i, j, dir, per;
This line declares the necessary variables: `w` and `h` for the width and height of the grid, `i` and `j` for the robot's current position, `dir` for the robot's current direction, and `per` for the perimeter of the grid.
2 : Constructor Definition
Robot(int width, int height) {
This is the constructor for the `Robot` class that initializes the robot's grid size (`w` and `h`), its starting position (`i` and `j`), its starting direction (`dir`), and calculates the perimeter of the grid.
3 : Width Initialization
w = width;
This line initializes the width of the grid with the input `width` value.
4 : Height Initialization
h = height;
This line initializes the height of the grid with the input `height` value.
5 : Initial Position
i = 0;
This line sets the robot's initial horizontal position (`i`) to 0 (top-left corner).
6 : Initial Position
j = 0;
This line sets the robot's initial vertical position (`j`) to 0 (top-left corner).
7 : Direction Initialization
dir = 0;
This line sets the robot's initial direction (`dir`) to 0, which represents East.
8 : Perimeter Calculation
per = 2 * (w + h - 2);
This line calculates the perimeter of the grid, which is used to optimize movement by limiting unnecessary steps.
9 : Step Function Definition
void step(int num) {
This function defines how the robot steps based on the input `num`, which represents the number of steps to move.
10 : Check for Perimeter Exceedance
if(num > per) {
This checks if the number of steps exceeds the perimeter of the grid. If so, it reduces the steps to stay within the perimeter.
11 : Modulo Adjustment
num %= per;
This line applies the modulo operation to `num` to ensure the number of steps does not exceed the perimeter.
12 : Initial Direction Adjustment
if(i == 0 && j == 0 && dir == 0) dir = 3;
This condition adjusts the direction to South if the robot starts at the top-left corner facing East.
13 : Movement Directions Setup
int mo[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
This array defines the movement directions: East, North, West, and South, using coordinate shifts.
14 : Movement Loop
while(num) {
This loop runs while there are steps left to take.
15 : Calculate New Position
int x = i + mo[dir][0], y = j + mo[dir][1];
This calculates the new position (`x`, `y`) based on the current direction of movement.
16 : Boundary Check
if(x >= w || y >= h || x < 0 || y < 0) {
This condition checks if the new position is outside the grid boundaries.
17 : Change Direction
dir = (dir + 1) % 4;
If the new position is outside the grid, the direction is updated to the next direction in the cycle (East -> North -> West -> South).
18 : Position Update
} else {
If the new position is within bounds, proceed to update the robot's position.
19 : Update Position
i = x;
This updates the robot's horizontal position (`i`).
20 : Update Position
j = y;
This updates the robot's vertical position (`j`).
21 : Step Decrement
num--;
This decrements the number of steps remaining.
Best Case: O(1)
Average Case: O(num)
Worst Case: O(num)
Description: The time complexity is proportional to the number of steps the robot takes, as each step is processed sequentially.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only store the robot's position and direction.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus