Bai toan di chuyen

Các bài toán di chuyển
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.
Các giá trị x0và y0, x1 và y1 có thể đạt tới 60 nghìn. Chương trình của Robot có thể bao gồm250 kí tự. Trục tung AB chứa toạ độ dòng x, trục hoành AD chứa toạ độ cột y.
Thí dụ:






ROBOT.INP
5 10
(D50Q2D50q3d50qD100)10d2



ROBOT.OUT
5 8




Bài giải
Trước hết ta mở tệp văn bản ROBOT.INP để đọc dữ liệu vàocác biến x0, y0 chứa toạ độ vị trí xuất phát của Robot và biến xâu kí tự s chứachương trình điều khiển Robot. Chươngtrình s, theo đầu bài chính là một lệnh phức. Ta sử dụng kỹ thuật hai pha đểphân tích chương trình của Robot thành các dòng lệnh ghi trong một bảng như Hình2. Các bạn có thể tham khảo bài Kỹ thuật hai pha trong số 7/2000.
Pha 1. Thủ tục xử lý LenhPhuc sẽ gọithủ tục LenhDon nếu gặp lệnh đơn dạng Cm vàgọi đệ quy LenhPhuc nếu gặp lệnh dạng (u)m,trong đó C là một trong bốn chữcái D, d, Q hoặc q, u là một lệnhphức, m là một số tự nhiên.


Chương trình sử dụng các hằng sau đây:
const
DauTu = [`(`,`Q`,`q`,`D`,`d`];
ChuSo = [`0`..`9`];
MN = 250;
DauTu là hằng kiểu tập chứa các kí tự đầu mỗi lệnh, trongđó( là dấu hiệu đầu của một lệnh phức, bốn chữ cái còn lại là dấu hiệu đầucủa