Robot Bounded In Circle trong C++

Giả sử có một mặt phẳng vô hạn, robot ban đầu đứng tại vị trí (0, 0) và hướng về phía Bắc. Robot có thể nhận 3 lệnh:

• G - tiến thẳng 1 đơn vị;

• L - quay trái 90 độ;

• R - quay phải 90 độ.

Robot thực hiện các lệnh theo thứ tự, và chuỗi lệnh lặp lại vô tận. Ta cần kiểm tra xem có tồn tại một đường tròn sao cho robot không bao giờ rời khỏi đường tròn đó. Ví dụ: đầu vào "GGLLGG", kết quả là true. Từ (0,0) đến (0,2), robot sẽ lặp lại mãi mãi, tạo thành đường đi khép kín.

Giải pháp:

• Tạo mảng hướng dir := [[0,1], [1,0], [0,-1], [-1,0]] (Bắc, Đông, Nam, Tây)

• Khởi tạo vị trí temp = (0, 0), k := 0 (chỉ số hướng)

• Duyệt qua từng ký tự trong chuỗi s:
  Nếu 'G': temp += dir[k]
  Nếu 'L': k = (k + 1) % 4
  Nếu 'R': k = (k - 1 + 4) % 4

• Trả về true nếu temp == (0,0) HOẶC k > 0 (robot quay về gốc hoặc không hướng về Bắc)

Ví dụ

#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;    } }; int main(){    Solution ob;    cout << (ob.isRobotBounded("GGLLGG")); }

Đầu vào

"GGLLGG"

Đầu ra

1