COCI 2016/2017 - Contest 5 - Strelice

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 5
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hansel và Gretel cùng nhau chơi một trò chơi nổi tiếng về những mũi tên trên bảng ô vuông gồm ~R~ dòng và ~S~ cột. Ở mỗi ô chỉ có một mũi tên duy nhất chỉ về một trong bốn hướng chính.

Hansel đi trước, nhiệm vụ của anh là tô màu chính xác ~K~ ô trên bảng sao cho những ô được tô không nằm ở cột cuối cùng. Sau đó, Gretel đặt một con robot tại một ô bất kì ở cột đầu tiên. Robot có thể tự di chuyển từ ô này sang ô khác theo hướng mà mũi tên chỉ dẫn. Nếu tại một thời điểm nào đó robot đến cột cuối cùng thì nó sẽ dừng lại và trò chơi kết thúc.

Người thắng cuộc của trò chơi được xác định như sau:

  • Nếu robot dừng lại và trò chơi kết thúc, Hansel là người chiến thắng nếu robot đi qua duy nhất một ô được tô màu. Ngược lại Gretel là người chiến thắng nếu robot không đi qua bất kì ô nào được tô màu hoặc đi qua nhiều hơn một ô được tô màu.
  • Nếu như robot không dừng lại sau một khoảng thời gian nhất định, nói cách khác nếu robot bị kẹt trong một vòng lặp vô hạn, Hansel là người chiến thắng.

Các mũi tên được vẽ sao cho robot không thể đi ra ngoài bảng.

Hensel không biết liệu anh ta có thể chiến thắng với mọi vị trí mà Gretel đặt robot. Nếu Hansel có thể chiến thắng hãy giúp anh ấy tìm ~K~ ô mà anh ấy cần tô màu để giành chiến thắng.

Input

Dòng đầu tiên chứa ba số nguyên ~R, S, K~ ~(1 \leq R\cdot S \leq 10^6,\: 1 \leq K \leq 50)~.

~R~ dòng tiếp theo, mỗi dòng gồm ~S~ ký tự, chỉ gồm các ký tự L, R, U, D thể hiện cho hướng của mũi tên trong ô đó (L - Trái, R - Phải, U - Lên, D - Xuống).

Output

Nếu Hansel có thể chiến thắng, hãy in ra ~K~ dòng, mỗi dòng gồm hai số nguyên ~A~ và ~B~ ~(1 \leq A \leq R,\: 1\leq B \leq S)~ là chỉ số dòng và chỉ số cột của ô mà Hansel cần tô màu. Mọi ô được tô đều phân biệt. Nếu có nhiều đáp án in ra một trong số chúng.

Ngược lại in ra -1.

Sample 1

Input
4 3 1 
DRD 
DUD 
DUD 
RUL
Output
4 2

Nếu Hansel tô màu ô ~(4,2)~ thì robot sẽ đi qua nó bất kể Gretel có đặt nó ở đâu đi nữa. Chính vì vậy Hansel là người chiến thắng.

Sample 2

Input
3 3 2 
RRR 
RRR 
RRR
Output
-1

Bởi vì Hansel phải tô màu chính xác hai ô, chắc chắn luôn có một dòng không chứa bất kì ô nào được tô màu. Gretel có thể đặt robot ở dòng đó và robot sẽ không đi qua ô nào được tô màu nên Gretel là người chiến thắng.

Sample 3

Input
4 4 2 
RRDL 
RRDL 
DLRD 
RRRL 
Output
2 3 
4 1

Ví dụ này được mô tả bằng hình ảnh phía trên đề.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.