[요약] 시작점에서 전파를 발사하여 가장 길게 보내려한다. 행성은 두 종류가 있는데 / 모양과 \ 모양이 있다. 행성에 모양에 따라 전파의 가는 방향은 다음과 같다.

우리는 어디로 발사하면 전파가 가장 멀리 갈지가 궁금하다. 가장 멀리 갈 수 있는 방향과 그때의 전파 이동 거리를 출력하자. 만약 전파가 빠져나오지 못한다면, 방향과 Voyager를 출력하자.

첫 번째 입력 예이다.( C 는 블랙홀 , . 은 빈 공간 , / 와 \ 는 행성을 나타낸다.)

여러개의 답이 가능하면 U(up),R(right),D(down),L(eft) 순으로 가능한 것을 먼저 출력 한다.

Let us assume that a star system can be represented by a rectangular grid with N rows and M columns, dividing the space into N by M equal cells. Each cell can contain a single planet, black hole, or be empty. The probe broadcasts the signal from a pre-determined empty cell, in one of the four axis-aligned directions (“U”-up, “R”-right, “D”-down, “L”-left).

Upon being broadcast, the signal propagates in a straight line along the same row/column until it reaches a planet, where it is deflected by 90 degrees in another direction. There are two kinds of planets, which we will denote by ?/“ and ?\“. The deflection rules are shown in the image below:

The signal permanently leaves the system upon either entring a cell containing a black hole, or propagating outside the edges of the rectangular grid. It is also known that the signal needs one second to propagate from the current cell to a neighbouring one.

Write a program to determine the direction in which the probe needs to broadcast the signal so that it remains within the system for as long as possible, outputting the optimal direction as well as the resulting longest time. If it is possible for the signal to remain in the system indefinitely, output the message ?Voyager“ instead of the required time.

입력

• The first line of input contains two positive integers, N (1 ≤ N ≤ 500) and M (1 ≤ M ≤ 500).
• Each of the following N lines contains M characters from the set {“/”, “\”, “C”, “.”}, where “/” and “\” represent the two kinds of planets, “C” represents a black hole, and “.” represents an empty cell.
• The last line of input contains two positive integers, PR (1 ≤ PR ≤ N) and PC (1 ≤ PC ≤ M), the row and column number, respectively, of the cell where the probe is situated.

출력

• The first line of output must contain the required optimal broadcast direction (“U”, “R”, “D”, or “L”). If the solution is not unique, select the first optimal one in the following priority order: first “U”, then “R”, then “D”, and finally “L”.
• The second line of output must contain the required longest time (or message)

입출력 예

input 

5 5 
../.\ 
..... 
.C... 
...C. 
\.../ 
3 3 

output 

U 
17 

input 

5 5 
....\ 
\..\. 
./\.. 
\../C 
.\../ 
1 1 

output 

D 
12 

input 

5 7 
/.....\ 
../..\. 
\...../ 
/.....\ 
\.\.../ 
3 3 

output 

R 
Voyager

출처:coci/2012-2013/contest4
요약:Fate