Robot Karel
Đề bài
Mô tả
Bạn có biết từ "robot" đã gần 100 tuổi? Từ này xuất hiện lần đầu năm 1920 trong vở kịch khoa học viễn tưởng R.U.R. của Karel Čapek. Để tưởng nhớ nhà văn Séc này, nhiều năm sau, Đại học Stanford đặt tên Karel cho một ngôn ngữ lập trình dùng trong giảng dạy. Nhiệm vụ của bạn là viết trình thông dịch cho một phiên bản đơn giản hóa của ngôn ngữ này.
Ngôn ngữ Karel điều khiển một robot tên Karel sống trong một lưới các ô vuông đơn vị. Một số ô trống, các ô khác có vật cản. Karel luôn đứng ở một ô trống và quay mặt về một trong bốn hướng chính. Hai lệnh cơ bản là "tiến lên" và "quay trái". Ngôn ngữ còn có lệnh rẽ nhánh và lệnh lặp đơn giản. Giá trị giáo dục chính của ngôn ngữ nằm ở khả năng định nghĩa thủ tục mới cho các công việc phức tạp hơn.
Phiên bản đơn giản hóa được mô tả bằng văn phạm sau:
<program> := "" | <command> <program>
<command> := "m" | "l" | <proc-call> |
"i" <condition> "(" <program> ")(" <program> ")" |
"u" <condition> "(" <program> ")"
<condition> := "b" | "n" | "s" | "e" | "w"
<proc-call> := <uppercase-letter>
<proc-def> := <uppercase-letter> "=" <program>
Có năm loại lệnh:
m("tiến lên"): Karel tiến một ô theo hướng đang quay mặt, trừ khi ô đó có vật cản; khi đó lệnh không có tác dụng.l("quay trái"): Karel quay trái độ.X, vớiXlà một chữ cái in hoa bất kỳ: gọi thủ tục tênX.i("nếu"), theo sau là một điều kiện một chữ cái và hai chương trình trong ngoặc. Nếu điều kiện thỏa mãn thì chương trình thứ nhất được thực hiện, ngược lại chương trình thứ hai được thực hiện.u("cho đến khi"), theo sau là một điều kiện một chữ cái và một chương trình trong ngoặc. Nếu điều kiện thỏa mãn thì không làm gì. Ngược lại, chương trình được thực hiện rồi lệnh này được lặp lại.
Điều kiện là b, thỏa mãn khi và chỉ khi ô kế tiếp theo hướng Karel đang quay mặt có vật cản, hoặc một trong bốn chữ chỉ hướng n, s, e, w, thỏa mãn khi và chỉ khi Karel đang quay mặt về hướng bắc, nam, đông, tây tương ứng.
Ví dụ, chương trình ub(m) có nghĩa là "tiến lên cho tới khi gặp vật cản", còn un(l) nghĩa là "quay về hướng bắc". Định nghĩa thủ tục R=lll tạo thủ tục mới R, thực chất là "quay phải".
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên , , và : và là kích thước lưới Karel sống, là số định nghĩa thủ tục, là số chương trình cần thực hiện.
Tiếp theo là dòng mô tả lưới (từ bắc xuống nam), mỗi dòng gồm ký tự (từ tây sang đông), mỗi ký tự là . (ô trống) hoặc # (vật cản). Mọi ô nằm ngoài vùng này đều được coi là vật cản, nghĩa là Karel không bao giờ rời khỏi vùng lưới.
Mỗi dòng trong dòng tiếp theo chứa một định nghĩa thủ tục, gắn một tên thủ tục (một chữ cái in hoa) với một chương trình làm thân thủ tục. Không có tên thủ tục nào được định nghĩa hai lần. Thân thủ tục có thể gọi các thủ tục được định nghĩa ở phía sau.
dòng cuối mô tả các chương trình cần thực hiện, mỗi chương trình gồm một cặp dòng. Dòng thứ nhất của mỗi cặp chứa hai số nguyên , và một ký tự : là hàng, là cột của vị trí xuất phát của Karel, n, s, e, w là hướng ban đầu. Vị trí xuất phát được đảm bảo là ô trống. Dòng thứ hai của mỗi cặp chứa chương trình cần thực hiện từ vị trí xuất phát đó.
Các dòng định nghĩa thủ tục và các dòng chương trình không chứa ký tự khoảng trắng.
Dữ liệu ra
Với mỗi lần thực hiện chương trình, in ra vị trí cuối cùng của Karel sau khi thực hiện xong toàn bộ chương trình từ vị trí xuất phát tương ứng, theo đúng định dạng mô tả vị trí xuất phát: hai số và một ký tự chỉ hướng. Nếu một lần thực hiện không bao giờ kết thúc, in ra inf.
Ràng buộc
- .
- .
- .
- , .
- Mọi thân thủ tục và mọi chương trình cần thực hiện dài từ đến ký tự, đúng cú pháp, và chỉ gọi các thủ tục đã được định nghĩa.
Ví dụ
Lưới của ví dụ thứ nhất (hàng ở trên cùng, cột ở bên trái):
grid .......# ..#....# .###...# .....###
| Input | Output | Giải thích |
|---|---|---|
| 4 8 5 7 .......# ..#....# .###...# .....### R=lll G=ub(B) B=ub(m)lib(l)(m) H=ib()(mmHllmll) I=III 1 1 w G 1 1 e G 2 2 n G 2 6 w BR 4 1 s ib(lib()(mmm))(mmmm) 1 1 e H 2 2 s I |
1 1 w inf 1 1 w 2 4 s 4 4 e 1 4 e inf |
Chương trình thứ nhất: phía tây ô là biên nên ub(B) dừng ngay. Chương trình thứ hai không bao giờ kết thúc: điều kiện dừng của vòng lặp ub(B) không bao giờ thỏa mãn. Chương trình cuối gọi I=III đệ quy vô hạn. |
| 2 3 1 4 ... .#. R=lll 1 1 e ub(m)R 2 1 w un(l)m 2 3 n ue(l)m 1 2 e us(m) |
1 3 s 1 1 n 2 3 e inf |
Chương trình thứ nhất: tiến tới rồi quay phải về hướng nam. Chương trình thứ hai: quay trái ba lần để về hướng bắc rồi tiến lên . Chương trình thứ ba: quay về hướng đông, ô phía đông là biên nên m không có tác dụng. Chương trình thứ tư: Karel quay mặt về hướng đông và không bao giờ quay về hướng nam. |
Bình luận