Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1041.html

1041. Robot Bounded In Circle (Medium)

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. 1 <= instructions.length <= 100
  2. instructions[i] is in {'G', 'L', 'R'}

Related Topics: Math

Solution 1.

  • class Solution {
        public boolean isRobotBounded(String instructions) {
            if (instructions == null || instructions.length() == 0)
                return true;
            int[][] directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
            int directionIndex = 0;
            int xPosition = 0, yPosition = 0;
            int length = instructions.length();
            for (int i = 0; i < length; i++) {
                char instruction = instructions.charAt(i);
                if (instruction == 'G') {
                    int[] direction = directions[directionIndex];
                    xPosition += direction[0];
                    yPosition += direction[1];
                } else if (instruction == 'L')
                    directionIndex = (directionIndex + 3) % 4;
                else if (instruction == 'R')
                    directionIndex = (directionIndex + 1) % 4;
            }
            return xPosition == 0 && yPosition == 0 || directionIndex != 0;
        }
    }
    
    ############
    
    class Solution {
        public boolean isRobotBounded(String instructions) {
            int[] direction = new int[4];
            int cur = 0;
            for (char c : instructions.toCharArray()) {
                if (c == 'L') {
                    cur = (cur + 1) % 4;
                } else if (c == 'R') {
                    cur = (cur + 3) % 4;
                } else {
                    ++direction[cur];
                }
            }
            return cur != 0 || (direction[0] == direction[2] && direction[1] == direction[3]);
        }
    }
    
  • // OJ: https://leetcode.com/problems/robot-bounded-in-circle/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        bool isRobotBounded(string instructions) {
            int x = 0, y = 0, d = 0, dir[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };
            for (int i = 0; i < 4; ++i) {
                for (char c : instructions) {
                    if (c == 'G') x += dir[d][0], y += dir[d][1];
                    else if (c == 'L') d = (d + 1) % 4;
                    else d = (d + 3) % 4;
                }
                if (x == 0 && y == 0) return true;
            }
            return false;
        }
    };
    
  • class Solution:
        def isRobotBounded(self, instructions: str) -> bool:
            cur, direction = 0, [0] * 4
            for ins in instructions:
                if ins == 'L':
                    cur = (cur + 1) % 4
                elif ins == 'R':
                    cur = (cur + 3) % 4
                else:
                    direction[cur] += 1
            return cur != 0 or (
                direction[0] == direction[2] and direction[1] == direction[3]
            )
    
    ############
    
    class Solution(object):
        def isRobotBounded(self, instructions):
            """
            :type instructions: str
            :rtype: bool
            """
            dirs = [(0, 1), (-1, 0), (0, -1), (1, 0)]
            x, y = 0, 0
            curd = 0
            for i in instructions:
                if i == "G":
                    x += dirs[curd][0]
                    y += dirs[curd % 4][1]
                elif i == "L":
                    curd = (curd + 1) % 4
                elif i == "R":
                    curd = (curd - 1) % 4
            return (x == 0 and y == 0) or curd != 0
    
  • func isRobotBounded(instructions string) bool {
    	direction := make([]int, 4)
    	cur := 0
    	for _, ins := range instructions {
    		if ins == 'L' {
    			cur = (cur + 1) % 4
    		} else if ins == 'R' {
    			cur = (cur + 3) % 4
    		} else {
    			direction[cur]++
    		}
    	}
    	return cur != 0 || (direction[0] == direction[2] && direction[1] == direction[3])
    }
    
  • function isRobotBounded(instructions: string): boolean {
        const dist: number[] = new Array(4).fill(0);
        let k = 0;
        for (const c of instructions) {
            if (c === 'L') {
                k = (k + 1) % 4;
            } else if (c === 'R') {
                k = (k + 3) % 4;
            } else {
                ++dist[k];
            }
        }
        return (dist[0] === dist[2] && dist[1] === dist[3]) || k !== 0;
    }
    
    

All Problems

All Solutions