COCI '16 Contest 5 #6 Strelice

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Hansel and Gretel are playing a well-known game of "Arrows" that takes place on a board with R rows and S columns. On each field there is exactly one arrow that points to one of the four main directions.

Hansel plays first, and his move is to colour exactly K fields on the board that are not located in the final column. Gretel then places a robot on an arbitrary field in the first column. Now the robot can move on his own, by moving from the current field to the field that the arrow points to. If at some point the robot is located in the last column, he stops and the game ends.

The winner of the game is determined in the following way:

  • If the robot stopped and the game ended, Hansel is the winner if the robot passed through exactly one coloured field, and Gretel is the winner if the robot passed through zero or more than one coloured fields.
  • If the robot did not stop after a finite amount of time (in other words, if the robot is stuck in an infinite loop), Hansel is the winner.

We consider that the robot passed through the starting field, through the fields it moved on throughout the game, and the field it was when the game ended. Also, the arrows will be drawn so that the robot never exists outside the board's boundaries.

Determine whether Hansel can ensure his victory no matter where Gretel initially places the robot. If the answer is positive, output K fields he can colour in order to win.

Input Specification

The first line of input contains the integers R, S, K (1 \le R \times S \le 1\,000\,000, 1 \le K \le 50).

Each of the following R lines contains S characters L, R, U, or D that denote the direction of the arrow in the corresponding field of the board (L - left, R - right, U - up, D - down).

Output Specification

If Hansel cannot ensure his victory, output -1.

If Hansel can ensure his victory, output K lines. In each line, output space-separated numbers A and B (1 \le A \le R, 1 \le B < S) that denote the row and column of the field that Hansel has to colour. All coloured fields must be different.

If multiple solutions exist, output any.

Sample Input 1

4 3 1
DRD
DUD
DUD
RUL

Sample Output 1

4 2

Explanation for Sample Output 1

If Hansel colours the field (4, 2), the robot will pass through it no matter where Gretel initially places it, so Hansel will be the winner.

Sample Input 2

3 3 2
RRR
RRR
RRR

Sample Output 2

-1

Explanation for Sample Output 2

Since Hansel must colour exactly 2 fields, this means that at least one of the three rows will not contain a coloured field. Gretel can place the robot in that row and it will pass through 0 coloured fields, so Gretel will win.

Sample Input 3

4 4 2
RRDL
RRDL
DLRD
RRRL

Sample Output 3

2 3
4 1

Explanation for Sample Output 3

Consult the image from the task.


Comments

There are no comments at the moment.