Robot Bounded In Circle C++

Suppose we have an infinite plane, a robot initially stands at position (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 direction;

• R − turn 90 degrees to the right direction.

The robot performs the instructions given in order, Instructions are repeated forever. We have to check whether there exists a circle in the plane such that the robot never leaves the circle. So if the input is like [GGLLGG], then the answer will be true. from (0,0) to (0,2), it will loop forever, so this is a closed path, and the answer is true.

To solve this, we will follow these steps −

• make an array dir := [[0,1], [1,0], [0,-1], [-1,0]]

• make a pair temp, and initially this is (0, 0) and k := 0

• for i in range 0 to size of s

  • if s[i] is G, then

    • temp := (dir[k, 0], dir[k, 1])

  • otherwise when s[i] is L, then k := (k + 1) mod 4, otherwise k := (k - 1) mod 4

• if false when temp is not (0, 0) and k > 0, otherwise true

Example

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; class Solution {    public:    bool isRobotBounded(string s) {       pair <int, int> temp({0,0});       int k = 0;       for(int i = 0; i < s.size(); i++){          if(s[i] == 'G'){             temp.first += dir[k][0];             temp.second += dir[k][1];          }else if(s[i] == 'L'){             k = (k + 1) % 4;          }else{             k = ((k - 1) + 4) % 4;          }       }       return temp.first == 0 && temp.second == 0 || k > 0;    } }; main(){    Solution ob;    cout << (ob.isRobotBounded("GGLLGG")); }

Input

"GGLLGG"

Output

1