Trong bài toán này, chúng ta cần xác định liệu một robot di chuyển trên mặt phẳng vô hạn có bị mắc kẹt trong một vòng lặp hay không. Robot bắt đầu tại vị trí (0, 0) và ban đầu hướng về phía Bắc.

Các lệnh mà robot có thể nhận được bao gồm:

• "G": Di chuyển về phía trước 1 đơn vị.
• "L": Rẽ trái 90 độ.
• "R": Rẽ phải 90 độ.

Mục tiêu là kiểm tra xem sau khi thực hiện chuỗi lệnh nhiều lần, robot có trở lại điểm xuất phát hoặc tạo thành một vòng lặp hay không. Nếu có, trả về true; ngược lại, trả về false.

Ví dụ minh họa:

<div>
    <strong>Ví dụ 1:</strong><br>
    Input: instructions = "GGLLGG"<br>
    Output: true<br>
    Giải thích: Sau khi thực hiện các lệnh, robot quay lại điểm xuất phát (0, 0), do đó kết quả là true.
</div>

<div>
    <strong>Ví dụ 2:</strong><br>
    Input: instructions = "GG"<br>
    Output: false<br>
    Giải thích: Robot tiếp tục di chuyển về phía Bắc và không tạo thành vòng lặp nào.
</div>

<div>
    <strong>Ví dụ 3:</strong><br>
    Input: instructions = "GL"<br>
    Output: true<br>
    Giải thích: Sau khi thực hiện các lệnh, robot quay lại điểm xuất phát và tạo thành một vòng lặp.
</div>

Giải pháp

Chúng ta sẽ sử dụng một mảng hai chiều để biểu diễn hướng di chuyển của robot và áp dụng phép tính toán tọa độ để kiểm tra điều kiện.

class Solution {
    public boolean isRobotBounded(String instructions) {
        // Mảng biểu diễn các hướng theo thứ tự: Bắc, Đông, Nam, Tây
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0; // Ban đầu robot hướng về phía Bắc
        int x = 0, y = 0;
        
        for (char command : instructions.toCharArray()) {
            if (command == 'G') {
                // Cập nhật tọa độ dựa trên hướng hiện tại
                x += directions[directionIndex][0];
                y += directions[directionIndex][1];
            } else if (command == 'L') {
                // Rẽ trái tương đương với việc giảm chỉ số hướng đi 1 bước
                directionIndex = (directionIndex + 3) % 4;
            } else if (command == 'R') {
                // Rẽ phải tương đương với việc tăng chỉ số hướng đi 1 bước
                directionIndex = (directionIndex + 1) % 4;
            }
        }

        // Kiểm tra nếu robot quay lại điểm xuất phát hoặc thay đổi hướng
        return (x == 0 && y == 0) || directionIndex != 0;
    }
}

Phân tích giải pháp

• Hướng di chuyển: Chúng ta sử dụng mảng directions để biểu diễn bốn hướng di chuyển chính: Bắc, Đông, Nam, Tây. Chỉ số directionIndex xác định hướng hiện tại của robot.
• Cập nhật tọa độ: Khi gặp lệnh "G", chúng ta cập nhật tọa độ (x, y) dựa trên hướng hiện tại.
• Quay trái/phải: Việc rẽ trái hoặc phải được thực hiện bằng cách thay đổi giá trị của directionIndex. Rẽ trái tương đương với việc trừ 1 từ chỉ số hướng, còn rẽ phải là cộng 1.
• Kiểm tra điều kiện vòng lặp: Sau khi thực hiện hết chuỗi lệnh, nếu robot quay lại điểm xuất phát hoặc thay đổi hướng so với ban đầu, nó sẽ tạo thành một vòng lặp.

Nguyên lý hoạt động

Nguyên nhân khiến robot tạo thành vòng lặp nằm ở tính chu kỳ của các phép quay và sự đối xứng trong các vector dịch chuyển:

• Nếu robot quay 180° (chỉ số hướng thay đổi từ Bắc sang Nam), chỉ cần lặp lại chuỗi lệnh hai lần là đủ để tạo thành vòng lặp.
• Nếu robot quay 90° hoặc 270° (chỉ số hướng thay đổi từ Bắc sang Đông hoặc Tây), lặp lại chuỗi lệnh bốn lần sẽ tạo thành một hình vuông đóng.

Điều này rất hữu ích trong các thuật toán lập bản đồ và quy hoạch đường đi cho robot như SLAM hoặc RRT*.