VOI 18 Bài 1 - Robot

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đọc đề gốc tại đây.

Chủ đề của cuộc thi ROBCON năm nay là "Tìm đường thoát mê cung". Tuấn vừa chế tạo được một robot để tham dự cuộc thi này. Tuấn rất thành thạo trong kỹ thuật chế tạo máy nhưng trong lập trình lại không được tốt như vậy. Do đó, Tuấn mới chỉ lập được một chương trình còn khá đơn giản để điều khiển robot của mình.

Robot di chuyển về phía trước với tốc độ 1 mét/giây cho đến khi gặp vật cản. Khi gặp vật cản robot sẽ liên tiếp thực hiện quay trái 90 độ cho đến khi trước mặt nó không có vật cản và lại tiếp tục di chuyển về phía trước. Thời gian để robot thực hiện đổi hướng chuyển động là cực nhanh, vì thế được coi là bằng 0. Robot không bao giờ tự dừng chuyển động.

Để thử nghiệm robot, Tuấn đã xây dựng một mê cung trên một mặt sàn thi đấu rất rộng lớn. Mặt sàn có dạng một lưới ô vuông kích thước ~1 \times 1~ mét. Các cột của lưới được đánh số bởi các số nguyên từ ~-10^{10}~ đến ~10^{10}~, từ trái qua phải. Các dòng của lưới được đánh số bởi các số nguyên từ ~-10^{10}~ đến ~10^{10}~, từ trên xuống dưới. Ô nằm trên giao của cột ~x~ và dòng ~y~ được gán với toạ độ ~(x, y)~. Mê cung mà Tuấn xây dựng là một lưới con kích thước ~N \times N~ với ô ở góc trái trên có toạ độ ~(1, 1)~. Trong một số ô của mê cung có đặt vật cản, các ô còn lại là ô rỗng (ô không có vật cản).

Tuấn đặt robot của mình vào ô có toạ độ ~(x, y)~, mặt robot quay về phía trên của lưới và cho robot chuyển động. Biết rằng vị trí mà Tuấn đặt robot không có vật cản và có ít nhất một ô chung cạnh với ô đặt robot là ô rỗng. Tuấn muốn xác định vị trí của robot sau ~S~ giây.

Yêu cầu: Hãy giúp Tuấn giải quyết vấn đề đặt ra.

Input

  • Dòng đầu tiên chứa bốn số nguyên ~N~, ~x~, ~y~, ~S~ được ghi cách nhau bởi dấu cách, ~1 \le N \le 1\,000, -10^5 \le x, y \le 10^5~;
  • ~N~ dòng tiếp theo mô tả mê cung, mỗi dòng gồm ~N~ ký hiệu được ghi liên tiếp nhau, mỗi ký hiệu được lấy từ tập {#, .}, trong đó ký hiệu # cho biết ô tương ứng trong mê cung có vật cản, còn ký hiệu . cho biết ô tương ứng trong mê cung là ô rỗng.

Output

Ghi ra hai số nguyên cách nhau bởi một dấu cách là toạ độ của ô mà robot đạt đến sau ~S~ giây.

Chú ý: Ô xuất phát và ô mà robot đạt đến sau ~S~ giây không nhất thiết phải nằm trong mê cung.

Giới hạn

  • Có ~50\%~ số lượng test ứng với ~50\%~ số điểm của bài thoả mãn điều kiện: ~1 \le S \le 10^5~.
  • ~50\%~ số lượng test còn lại ứng với ~50\%~ số điểm của bài thoả mãn điều kiện: ~1 \le S \le 10^9~.

Sample Input 1

4 3 5 9
###.
#...
#..#
##.#

Sample Output 1

2 3

Sample Input 2

3 2 5 7
###
#..
#..

Sample Output 2

2 6

Note

Giải thích: Hình 1a) dưới đây minh hoạ cho ví dụ thứ nhất. Lưới con gồm các ô được tô nền xanh là mê cung. Đường di chuyển của robot xuất phát từ ô ~(3, 5)~ (ô có chữ R) qua các ô của sàn thi đấu được chỉ ra bởi các mũi tên. Trong ví dụ này ô xuất phát không thuộc mê cung. Sau ~9~ giây, robot đạt đến ô ~(2, 3)~.

Tương tự, hình 1b) minh hoạ đường di chuyển của robot trong ví dụ thứ hai: Robot xuất phát từ ô ~(2, 5)~, đạt đến ô ~(2, 6)~ sau ~7~ giây.

image

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.


There are no comments at the moment.