Chương trình kiểm tra robot di chuyển trong hộp giới hạn Python

Cho chuỗi s biểu diễn lệnh robot: 'F' (tiến 1), 'L' (xoay trái 90°), 'R' (xoay phải 90°). Robot bắt đầu tại (0,0) hướng Bắc. Nếu lặp lại chuỗi lệnh vô hạn, kiểm tra robot có bị giới hạn trong một hộp hữu hạn không.

Ví dụ: s="FFRFRFFRF" → True (robot tạo thành hình vuông).

Giải thuật (Mô phỏng 4 chu kỳ)

1. Mô phỏng robot chạy 4 lần chuỗi lệnh
2. Nếu sau 4 chu kỳ robot quay về (0,0) → bị giới hạn (True)
3. Ngược lại → đi xa vô hạn (False)

Lý do: sau 4 lần xoay, hướng robot quay về hướng ban đầu. Nếu không về gốc tọa độ thì dịch chuyển mỗi chu kỳ là vector không нуль → đi xa vô hạn.

Ví dụ triển khai

def solve(s):
    moves = [[0, -1], [1, 0], [0, 1], [-1, 0]]  # Bắc, Đông, Nam, Tây
    r, c = 0, 0
    d = 0  # 0=Bắc, 1=Đông, 2=Nam, 3=Tây
    for _ in range(4):
        for ch in s:
            if ch == "F":
                r, c = r + moves[d][0], c + moves[d][1]
            elif ch == "L":
                d = (d + 3) % 4
            elif ch == "R":
                d = (d + 1) % 4
        if r == 0 and c == 0:
            return True
    return False

print(solve("FFRFRFFRF"))

Đầu vào

"FFRFRFFRF"

Đầu ra

True