On an infinite plane, a robot initially stands at (0, 0)
and faces north. The robot can receive one of three instructions:
"G"
: go straight 1 unit;"L"
: turn 90 degrees to the left;"R"
: turn 90 degress to the right.
The robot performs the instructions
given in order, and repeats them forever.
Return true
if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
Input: "GGLLGG" Output: true Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
Input: "GG" Output: false Explanation: The robot moves north indefinitely.
Example 3:
Input: "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Note:
1 <= instructions.length <= 100
instructions[i]
is in{'G', 'L', 'R'}
Solution: Simulation
When instructions end, if the robot is back to (0,0) or is not facing north (which guarantees it will come back to 0, 0 for another 1 or 3 rounds)
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: bool isRobotBounded(string instructions) { int x = 0; int y = 0; int d = 0; vector<int> dx{0, 1, 0, -1}; vector<int> dy{-1, 0, 1, 0}; for (char c : instructions) { if (c == 'G') { x += dx[d]; y += dy[d]; } else { d = (d + (c == 'L' ? 3 : 1)) % 4; } } return x == 0 && y == 0 || d; } }; |