Tôi đang ở đâu?
Đề bài
Mô tả
Đây là bài toán tương tác.
Tôi là ai? Tôi là gì? Vì sao tôi tồn tại? Đó đều là những câu hỏi khó đã khiến các triết gia bận rộn suốt hàng thiên niên kỷ qua. Nhưng với câu hỏi "Tôi đang ở đâu?" thì điện thoại thông minh và vệ tinh GPS hiện đại đã lấy đi gần hết sự thú vị.
Nhưng nếu trong tay bạn không có GPS thì sao? Trong một bài của World Finals 2021, Công ty Định vị Bản đồ Tức thời (ICPC) đã trình diễn một cách xác định vị trí hiện tại bằng cách đi theo hình xoắn ốc và quan sát xung quanh. Đáng tiếc, phương pháp đó chỉ dùng được ở vùng trống, nơi có thể đi lại tự do không có vật cản. Nếu bạn cần xác định chính xác vị trí của mình trong một không gian kín thì sao? Làm thế nào? Giờ là lúc tìm câu trả lời.
Bạn được cho bản đồ của một khu vực gồm các ô vuông đơn vị, mỗi ô hoặc là ô trống, hoặc là ô có tường. Lúc đầu, bạn được đặt tại một ô trống nào đó, nhưng bạn không biết đó là ô nào, cũng không biết mình đang quay mặt về hướng nào. Hai ô trống bất kỳ là không phân biệt được với nhau, hai ô tường cũng vậy. Bạn có thể đi lại trong khu vực, và ở mỗi bước bạn quan sát được khoảng cách tới bức tường gần nhất theo hướng mình đang nhìn. Mục tiêu là xác định chính xác vị trí của bạn trên bản đồ.
Tương tác
Dòng đầu tiên của dữ liệu vào chứa hai số nguyên và (), kích thước bản đồ. Tiếp theo là dòng, mỗi dòng gồm ký tự. Mỗi ký tự hoặc là dấu chấm (.) chỉ một ô trống, hoặc là dấu thăng (#) chỉ một ô có tường.
Có ít nhất một ô trống. Bạn biết mình bắt đầu tại một trong các ô trống của bản đồ, quay mặt về một trong bốn hướng chính (bắc, đông, nam, tây; bắc là phía dòng ), nhưng vị trí và hướng của bạn không được cho trong dữ liệu vào. Mọi ô nằm ngoài bản đồ đều được coi là tường.
Sau đó tương tác diễn ra theo từng lượt. Ở mỗi lượt, chương trình của bạn đọc một dòng chứa một số nguyên (): phía trước mặt bạn có tường ở khoảng cách , nghĩa là có đúng ô trống nằm giữa ô của bạn và bức tường gần nhất theo hướng hiện tại. Sau đó chương trình của bạn in ra một dòng chứa một trong các lệnh sau:
left: quay trái độ,right: quay phải độ,step: tiến một ô theo hướng hiện tại,yes i j: khẳng định vị trí hiện tại của bạn là dòng , cột (, ),no: khẳng định rằng dù bạn làm gì đi nữa, cũng không thể xác định chắc chắn vị trí của mình.
Nếu bạn in yes hoặc no, tương tác kết thúc và chương trình của bạn phải dừng. Ngược lại, một lượt mới bắt đầu. Để được chấp nhận, chương trình của bạn không bao giờ được bước vào tường, và chỉ được chạy nhiều nhất lượt tương tác (lượt cuối cùng, khi bạn chỉ trả lời yes hoặc no, cũng được tính vào giới hạn này).
Câu trả lời phải chắc chắn: yes i j chỉ được chấp nhận nếu mọi cách đặt ban đầu (ô và hướng) khớp với tất cả các khoảng cách bạn đã quan sát đều đang ở ô ; no chỉ được chấp nhận nếu với mọi cách đặt ban đầu như vậy, thực sự không có cách nào xác định chắc chắn vị trí.
Sau mỗi lần in, đừng quên xuống dòng và flush đầu ra: dùng cout << endl hoặc cout.flush() trong C++, sys.stdout.flush() trong Python.
Ràng buộc
- , bản đồ có ít nhất một ô trống.
- Nhiều nhất lượt tương tác.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 ##. #.. ... 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 2 1 0 2 1 0 0 |
left left left step left left left left left step left left left step left left step step left step step right yes 1 3 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Vị trí ban đầu bí mật là dòng , cột , quay mặt về hướng nam. Chương trình đi khắp vùng trống (vùng này không có đối xứng quay), nên biết chắc mình đang ở ô . Đề gốc minh họa một cách đi ngắn hơn với một vị trí ban đầu khác. |
| 3 5 ##.## ###.# .#.## 0 0 0 0 |
left left left no |
Mọi ô trống đều bị tường bao quanh cả bốn phía nên trông giống hệt nhau: không thể biết mình ở ô nào. |
| 2 1 # . 0 0 0 0 |
left left left yes 2 1 |
Chỉ có một ô trống. Thực ra có thể trả lời yes 2 1 ngay ở lượt đầu tiên. |
Bình luận