1041. Robot Bounded In Circle
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'.
Solution:
class Solution {
public boolean isRobotBounded(String instructions) {
int[][] dir = {{0, 1}, {1,0}, {0, -1}, {-1, 0}};
// up right down left
int r = 0;
int x = 0;
int y = 0;
for (int i = 0; i < instructions.length(); i++){
if (instructions.charAt(i) == 'L'){
r = (r + 3) % 4;
}else if (instructions.charAt(i) == 'R'){
r = (r + 1) % 4;
}else{
x = x + dir[r][0];
y = y + dir[r][1];
}
}
if (x == 0 && y == 0){
return true;
}else if (r != 0){
return true;
}else{
return false;
}
}
}
// TC: O(n)
// SC: O(1)
class Solution {
public boolean isRobotBounded(String instructions) {
int[][] dir = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
int r = 0;
// we have to keep tracking those cases where it's not rotating
// if in the end of execution, we see it's not rotating we will gonna return false;
int x = 0;
int y = 0;
for (int i = 0; i < instructions.length(); i++){
if (instructions.charAt(i) == 'L'){
r = (r + 1) % 4;
}else if (instructions.charAt(i) == 'R'){
r = (r + 3) % 4;
}else{
x = x + dir[r][0];
y = y + dir[r][1];
}
}
return x == 0 && y == 0 || r != 0;
}
}
class Solution {
public boolean isRobotBounded(String instructions) {
int[] pos = new int[]{0,0};
// Map<Integer, Set<Integer>> map = new HashMap<>();
// map.put(0, new HashSet<>());
// map.get(0).add(0);
int upCount = 1;
int downCount = 0;
int leftCount = 0;
int rightCount = 0;
for (int i = 0; i < instructions.length(); i++){
char cur = instructions.charAt(i);
if (cur == 'G'){
if (upCount == 1){
pos[1]++;
//upCount--;
// if (map.containsKey(pos[0]) && map.get(pos[0]).contains(pos[1])){
// return true;
// }else{
// map.getOrDefault(pos[0], new HashSet<>());
// map.get(pos[0]).add(pos[1]);
// }
}else if (downCount == 1){
pos[1]--;
//downCount--;
// if (map.containsKey(pos[0]) && map.get(pos[0]).contains(pos[1])){
// return true;
// }else{
// map.getOrDefault(pos[0], new HashSet<>());
// map.get(pos[0]).add(pos[1]);
// }
}else if (leftCount == 1){
pos[0]--;
//leftCount--;
// if (map.containsKey(pos[0]) && map.get(pos[0]).contains(pos[1])){
// return true;
// }else{
// map.getOrDefault(pos[0], new HashSet<>());
// map.get(pos[0]).add(pos[1]);
// }
}else if (rightCount == 1){
pos[0]++;
// if (map.containsKey(pos[0]) && map.get(pos[0]).contains(pos[1])){
// return true;
// }else{
// map.getOrDefault(pos[0], new HashSet<>());
// map.get(pos[0]).add(pos[1]);
// }
}
}else if (cur == 'L'){
if (upCount == 1){
upCount = 0;
leftCount = 1;
}else if (leftCount == 1){
leftCount = 0;
downCount = 1;
}else if (downCount == 1){
downCount = 0;
rightCount = 1;
}else if (rightCount == 1){
rightCount = 0;
upCount = 1;
}
}else{
// 'R'
if (upCount == 1){
upCount = 0;
rightCount = 1;
}else if (leftCount == 1){
leftCount = 0;
upCount = 1;
}else if (downCount == 1){
downCount = 0;
leftCount = 1;
}else if (rightCount == 1){
rightCount = 0;
downCount = 1;
}
}
}
if (pos[0] == 0 && pos[1] == 0 || upCount != 1){
return true;
}else{
return false;
}
}
}
// 第一次的时候题意理解错了