Robot bị ràng buộc trong vòng tròn C ++

Giả sử chúng ta có một mặt phẳng vô hạn, một robot ban đầu đứng ở vị trí (0, 0) và quay mặt về hướng bắc. Robot có thể nhận một trong ba hướng dẫn -

G - đi thẳng 1 đơn vị;
L - quay 90 độ sang hướng trái;
R - quay 90 độ về hướng bên phải.

Robot thực hiện các hướng dẫn được đưa ra theo thứ tự, Các hướng dẫn được lặp lại mãi mãi. Chúng ta phải kiểm tra xem có tồn tại một vòng tròn trong mặt phẳng để robot không bao giờ rời khỏi vòng tròn đó hay không. Vì vậy, nếu đầu vào là [GGLLGG], thì câu trả lời sẽ là true. từ (0,0) đến (0,2), nó sẽ lặp lại mãi mãi, vì vậy đây là một đường dẫn đóng và câu trả lời là đúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

tạo mảng dir:=[[0,1], [1,0], [0, -1], [-1,0]]
tạo một cặp tạm thời và ban đầu đây là (0, 0) và k:=0
cho tôi trong phạm vi từ 0 đến kích thước của s
- nếu s [i] là G thì
  - tạm thời:=(dir [k, 0], dir [k, 1])
- ngược lại khi s [i] là L thì k:=(k + 1) mod 4, ngược lại k:=(k - 1) mod 4
nếu sai khi nhiệt độ không (0, 0) và k> 0, ngược lại là đúng

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"GGLLGG"

Robot bị ràng buộc trong vòng tròn C ++

Ví dụ

Đầu vào

Đầu ra