Description
On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:
- The north direction is the positive direction of the y-axis.
- The south direction is the negative direction of the y-axis.
- The east direction is the positive direction of the x-axis.
- The west direction is the negative direction of the x-axis.
The robot can receive one of three instructions:
"G": go straight 1 unit."L": turn 90 degrees to the left (i.e., anti-clockwise direction)."R": turn 90 degrees to the right (i.e., clockwise direction).
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: instructions = "GGLLGG" Output: true Explanation: The robot is initially at (0, 0) facing the north direction. "G": move one step. Position: (0, 1). Direction: North. "G": move one step. Position: (0, 2). Direction: North. "L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West. "L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South. "G": move one step. Position: (0, 1). Direction: South. "G": move one step. Position: (0, 0). Direction: South. Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0). Based on that, we return true.
Example 2:
Input: instructions = "GG" Output: false Explanation: The robot is initially at (0, 0) facing the north direction. "G": move one step. Position: (0, 1). Direction: North. "G": move one step. Position: (0, 2). Direction: North. Repeating the instructions, keeps advancing in the north direction and does not go into cycles. Based on that, we return false.
Example 3:
Input: instructions = "GL" Output: true Explanation: The robot is initially at (0, 0) facing the north direction. "G": move one step. Position: (0, 1). Direction: North. "L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West. "G": move one step. Position: (-1, 1). Direction: West. "L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South. "G": move one step. Position: (-1, 0). Direction: South. "L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East. "G": move one step. Position: (0, 0). Direction: East. "L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North. Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0). Based on that, we return true.
Constraints:
1 <= instructions.length <= 100instructions[i]is'G','L'or,'R'.
Solutions
Solution 1: Simulation
We can simulate the robot's movement. Use a variable k to represent the robot's direction, initialized to 0, which means the robot is facing north. The variable k can take values in the range [0, 3], representing the robot facing north, west, south, and east, respectively. Additionally, we use an array dist of length 4 to record the distance the robot travels in the four directions, initialized to [0, 0, 0, 0].
Traverse the instruction string instructions. If the current instruction is 'L', the robot turns west, i.e., k = (k + 1) \bmod 4; if the instruction is 'R', the robot turns east, i.e., k = (k + 3) \bmod 4; otherwise, the robot moves one step in the current direction, i.e., dist[k]++.
If the given instruction string instructions is executed once and the robot returns to the origin, i.e., dist[0] = dist[2] and dist[1] = dist[3], then the robot will definitely enter a loop. This is because no matter how many times the instructions are repeated, the robot always returns to the origin, so it must enter a loop.
If the given instruction string instructions is executed once and the robot does not return to the origin, suppose the robot is at (x, y) and its direction is k.
- If k=0, i.e., the robot is facing north, then after executing the instructions a second time, the coordinate change is (x, y); after executing the instructions a third time, the coordinate change is still (x, y)... Accumulating these changes, the robot will eventually reach (n × x, n × y), where n is a positive integer. Since the robot does not return to the origin, i.e., x ≠ 0 or y ≠ 0, it follows that n × x ≠ 0 or n × y ≠ 0, so the robot will not enter a loop;
- If k=1, i.e., the robot is facing west, then after executing the instructions a second time, the coordinate change is (-y, x); after executing the instructions a third time, the coordinate change is (-x, -y); after executing the instructions a fourth time, the coordinate change is (y, -x). Accumulating these coordinate changes, we find that the robot will eventually return to the origin (0, 0);
- If k=2, i.e., the robot is facing south, then after executing the instructions a second time, the coordinate change is (-x, -y). Accumulating these two coordinate changes, we find that the robot will eventually return to the origin (0, 0);
- If k=3, i.e., the robot is facing east, then after executing the instructions a second time, the coordinate change is (y, -x); after executing the instructions a third time, the coordinate change is (-x, -y); after executing the instructions a fourth time, the coordinate change is (-y, x). Accumulating these coordinate changes, we find that the robot will eventually return to the origin (0, 0).
In conclusion, if the given instruction string instructions is executed once and the robot returns to the origin, or if the robot's direction is different from the initial direction, then the robot will definitely enter a loop.
The time complexity is O(n), and the space complexity is O(1), where n is the length of the instruction string instructions.
class Solution: def isRobotBounded(self, instructions: str) -> bool: k = 0 dist = [0] * 4 for c in instructions: if c == 'L': k = (k + 1) % 4 elif c == 'R': k = (k + 3) % 4 else: dist[k] += 1 return (dist[0] == dist[2] and dist[1] == dist[3]) or k != 0(code-box)
