To those who are getting wrong answer by calculating the extreme x and y position:
Your approach only checks for extreme x and y position, ie. the maximum displacement from a block rather one should consider the range or the distance that the robot travels.
Consider this test case for example-
According to your code, by finding abs(x max) it is 2, so it should be safe, but actually it isn’t-
Let me try and draw a picture here-
1 | 2 | 3 | 4 |
Now, if lets start at each position and see, whether the robot can be safe or not-
Block 1, the left limit runs out of bounds.
Block 2, the left limit runs out of bounds.
Block 3, the right limit runs out of bounds.
Block 4, the right limit runs out of bounds.
So, the answer should be “unsafe” but by calculating it your way, ie. calculating the extreme right and left limits is the wrong approach here.
Here what you are doing is, you are considering yourself to be in the middle, of a 2x grid, ie. with m columns on both right and left.
Even for this command, your code gives “safe”- RRRLLLLLL, but we all know that’s wrong.
In addition, there is an O(|s|) time solution that considers the maximum distance the robot travels up, down, right, and left from the original point. This avoids simulating from every starting grid square, since we know that the simulation will look very similar for those starting squares. Please look at the setter’s solution for more details.
See, it mentions maximum distance and not displacement, which you are calculating. Physics.
EDIT: What you are doing is calculating displacement and checking it for two different blocks, for right displacement, you are taking into consideration block 1 and for left displacement you are talking into consideration block 4, and merging the answers. This approach is write if a specific block is given, since we know what lies to it’s left and what lies to it’s right, but not here.