Wednesday, July 17, 2019

Leetcode 1041. Robot Bounded In Circle

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'}
Code (Java):
class Solution {
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int curX = 0;
    int curY = 0;
    int curDir = 0;    
    public boolean isRobotBounded(String instructions) {
        if (instructions == null || instructions.length() == 0) {
            return true;
        }
        

        for (int count = 0; count < 4; count++) {
            for (int i = 0; i < instructions.length(); i++) {
                char c = instructions.charAt(i);
                if (c == 'G') {
                    move();    
                } else {
                    turn(c);
                }
            }
        }
        
        return curX == 0 && curY == 0;
    }
    
    private void move() {
        curX += dirs[curDir][0];
        curY += dirs[curDir][1];
    }
    
    private void turn(char dir) {
        int dirVal = (dir == 'L' ? -1 : 1);
        curDir = (curDir + 4 + dirVal) % 4;
    }
}


No comments:

Post a Comment