Các bài toán di chuyển
Nguyễn Xuân Huy
Trong các kỳ thi học sinhgiỏi ta thường gặp một số bài toán có yếu tố di chuyển. Nội dung của những bàitoán này thường được phát biểu như sau: MộtRobot di chuyển trong một mê cung hình chữ nhật ABCD được chia thành các ôvuông đơn vị. Gốc toạ độ đặt tại điểm A (0,0). Robot đứng tại điểm R(x0,y0) làvị trí xuất phát, mặt hướng về phíaBắc, tức là nhìn về phía cạnh BC như trong Hình 1. Biết luật di chuyển củaRobot, hãy xác định vị trí kết thúc của Robot.
Bài toán trên có thể được bổ sung thêm một số điều kiệnnhư đặt năng lượng hoặc đặt bẫy tại một số ô. Nếu Robot gặp năng lượng thì sựvận động của nó sẽ mạnh hơn, chẳng hạn mỗi bước đi của nó có thể qua 2 ô, ngượclại, khi Robot gặp bẫy, sức khoẻ của nó suy giảm, bước di chuyển của nó sẽ ngắnhơn trước. Bố trí thêm các bức tường ngăn để tạo mê cung, ta có thể biến hoábài toán thành nhiều dáng vẻ khác nhau. Đương nhiên người ta khôngbịa ranhững bài toán để hành hạ học sinh. Đây là những bài toán điều khiển Robot cóthực trong đời thường. Giải hoặc làm chủ được các thuật toán di chuyển nói trênchúng ta sẽ có thể có những đóng góp giá trị cho lĩnh vực điều khiển Robot.
Sau đây xin giới thiệu với bạn đọc một bài toán cỡ trungbình trong số các bài toán điều khiển Robot.
Bài toán (Robot):Một Robot di chuyển trên một nền phẳngchia thành lưới toạ độ nguyên ABCD như Hình 1. Gốc toạ độ đặt tại điểm Ă0,0).Robot xuất phát từ điểm R(x0,y0), mặt hướng về phía cạnh BC gọi là hướng Bắc vàđi theo một chương trình lập sẵn.
Yêu cầu: Xácđịnh điểm kết thúc T(x1,y1) của Robot sau khi hoàn thành chương trình dichuyển.
Chương trình lậpsẵn cho Robot là một xâu kí tự bao gồm một dãy các lệnh dạng Cm, được gọi làlệnh đơn, hoặc (u)m, trong đó C là mộttrong các chữ cái Q, q, D hoặc d, m là một số tự nhiên, u là một lệnh phức đượctạo từ một dãy lệnh đơn hoặc lệnh phức. Các lệnh đơn có ý nghĩa như sau:
+ Dm: Tiến về phia trước m bước, mỗi bước là một lần di chuyển từ mộtđiểm đến điểm kế tiếp theo hướng nhìn của Robot.
+ dm: Lùi về phía sau m bước.
+ Qm: Quay người m lần, mỗi lần quay một góc 45 độ theo chiều kim đồnghồ.
+ qm: Quay người m lần, mỗi lần một góc 45 độ ngược chiều kim đồng hồ.
+ (u)m: thực hiện m lần dãy lệnh u.
Ta quy ước, nếum = 1 thì có thể không viết giá trị m. Nếu m = 0 thì đoạn lệnh tương ứng đặttrước m được bỏ qua.
Dữ liệu vào: Tệpvăn bảnROBOT.INP gồm 2 dòng.
+ Dòng thứ nhất: hai số tự nhiên x0 y0 cách nhau bởi dấu cách cho biếtvị trí xuất phát của Robot.
+ Dòng thứ hai: Chương trình điều khiển Robot.
Dữ liệu ra: Tệpvăn bản ROBOT.OUT gồm 1 dòng chứa hai số tự nhiên x1 y1cách nhau bởi dấu cáchcho biết vị trí kết thúc của Robot sau khi hoàn thành chương trình di chuyển.
