1041. Robot Bounded In Circle

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: instructions = "GGLLGG" Output: true

Input: instructions = "GG" Output: false

Input: instructions = "GL" Output: true

Solution Approach

After processing all instructions once, if the robot is either back at the starting position (0, 0) or facing a direction other than north, it will be bounded in a circle when the instructions are repeated indefinitely.

Algorithm

1. Initial Position and Direction: The robot starts at the origin (0, 0) facing north, with directions defined for north, east, south, and west.
2. Instruction Processing: For each instruction, the robot updates its position for ‘G’ (go straight) or changes its direction for ‘L’ (turn left) and ‘R’ (turn right), keeping the direction index within bounds using modulo operations.
3. Final State Check: After processing all instructions, the robot is bounded in a circle if it returns to the starting position (0, 0) or is facing a direction other than north.

Implement

    class Solution:
        def isRobotBounded(self, instructions: str) -> bool:
            #.        n
            #.     w     e
            #         s
            directions = [(0,1),(1,0),(0,-1),(-1,0)]
            visited = {}
            dirt = 0
            x, y = 0, 0
            for instr in instructions:
                if instr == 'G':
                    x += directions[dirt][0]
                    y += directions[dirt][1]
                elif instr == 'L':
                    dirt -= 1
                    dirt %= 4
                else:
                    dirt += 1
                    dirt %= 4
            return dirt != 0 or (x == 0 and y == 0)

    
    

Twitter  facebook  Email