/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
縦 H マス \times 横 W マスのマス目があり、高橋君はこのマス目を上下左右に移動します。
上から i 番目かつ左から j 番目 (1\leq i\leq H, 1\leq j\leq W) のマスの状態は文字 S_{i,j} で表されます。
S_{i,j} は #, ., o, x, S, G のいずれかです。
- S_{i,j}=
#のとき：このマスに立ち入ることはできない。 - S_{i,j}=
.のとき：このマスに自由に出入りすることができる。すなわち、このマスに立ち入った後、上下左右に隣接する好きなマスに（存在するならば）移動できる。 - S_{i,j}=
oのとき：このマスでは 直前の移動と同じ方向に移動しなければならない。すなわち、このマスに立ち入った後は、方向を変えずに次のマスへ移動しなければならない。 - S_{i,j}=
xのとき：このマスでは 直前の移動と同じ方向に移動することはできない。すなわち、このマスに立ち入った後は、必ず方向を変えて次のマスへ移動しなければならない。なお、180 度方向を変えて元のマスに戻ることは方向を変えて移動することに含まれる。 - S_{i,j}=
Sのとき：このマスは高橋君が最初にいる地点である。このマスは自由に出入りすることができる。 - S_{i,j}=
Gのとき：このマスは高橋君の目的地である。このマスは自由に出入りすることができる。
なお、S_{i,j}=S, G であるような (i,j) は 1\leq i\leq H, 1\leq j\leq W の範囲にちょうど 1 つずつ存在します。
高橋君は最初にいる地点から、上下左右に隣接するマスへの移動を繰り返して、目的地へと到達したいです。
そのような事が可能か判定し、可能ならば条件をみたす移動方法であって、隣接するマスへの移動回数が 5\times 10^6 以下であるようなものを一つ出力してください。
なお、問題の条件下において条件をみたす移動が可能ならば、そのような方法であって移動回数が 5\times 10^6 以下であるようなものが存在することが証明できます。
また、移動回数が 5\times 10^6 以下である限り、回数を最小化する必要はありません。
制約
- 1 \leq H,W\leq 1000
- S_{i,j} は
#,.,o,x,S,Gのいずれかである。 - S_{i,j}=
S,Gとなる (i,j) がちょうど一つずつ存在する。 - H,W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}
出力
条件をみたすように移動することが不可能ならば、1 行目に No を出力し、2 行目には何も出力してはならない。
条件をみたすように移動することが可能ならば、1 行目に Yes を出力せよ。
2 行目には移動方法を表す文字列 T を出力せよ。T は次の条件をすべてみたす必要がある。
- T の長さ \lvert T\rvert は 1 以上 5\times 10^6 以下である。
- T の各文字は
U,D,L,Rのいずれかである。- T の i 文字目が
U・D・L・Rであることはそれぞれ、高橋君が出発してから i 回目の移動で上・下・左・右に隣接するマスに移動することを表す。
- T の i 文字目が
- 1\leq i\leq \lvert T\rvert について、i 回目の移動の後で高橋君がマス目の外に出ることはない。
- 移動の途中で各マスの条件に違反しない。
- \lvert T\rvert 回目の移動の後で、高橋君は目的地のマスにいる。なお、この条件を満たしている限り、\lvert T\rvert 回目の移動より前に目的地のマスを通り過ぎていても良い。
入力例 1
3 5 .#... .Sooo ..x.G
出力例 1
Yes DRUUDDRR
上から i 番目かつ左から j 番目のマスをマス (i,j) で表します。
出力例にしたがって進むと、マス (2,2) \to マス (3,2) \to マス (3,3) \to マス (2,3) \to マス (1,3) \to マス (2,3) \to マス (3,3) \to マス (3,4) \to マス (3,5) のように移動し、目的地に到着します。
他に、DRUURLRRDD なども正解となります。
一方で、マス (3,3) を直進することはできないため、DRRR などは正解になりません。
入力例 2
3 3 #So xoG ..#
出力例 2
Yes DDLURR
入力例 3
2 2 So oG
出力例 3
No
条件をみたすように移動することはできません。
Score : 425 points
Problem Statement
There is a grid of H rows \times W columns, and Takahashi moves through this grid up, down, left, and right.
The state of the cell at the i-th row from the top and j-th column from the left (1\leq i\leq H, 1\leq j\leq W) is represented by the character S_{i,j}.
S_{i,j} is one of #, ., o, x, S, G.
- If S_{i,j}=
#: This cell cannot be entered. - If S_{i,j}=
.: This cell can be freely entered and exited. That is, after entering this cell, Takahashi can move to any adjacent cell (if it exists) in the up, down, left, or right direction. - If S_{i,j}=
o: In this cell, Takahashi must move in the same direction as the immediately preceding move. That is, after entering this cell, he must move to the next cell without changing direction. - If S_{i,j}=
x: In this cell, Takahashi cannot move in the same direction as the immediately preceding move. That is, after entering this cell, he must change direction to move to the next cell. Turning 180 degrees to return to the previous cell is considered as changing direction. - If S_{i,j}=
S: This cell is Takahashi's starting position. This cell can be freely entered and exited. - If S_{i,j}=
G: This cell is Takahashi's destination. This cell can be freely entered and exited.
There is exactly one (i,j) with 1\leq i\leq H, 1\leq j\leq W satisfying S_{i,j}=S, and exactly one satisfying S_{i,j}=G.
Takahashi wants to reach the destination by repeatedly moving to adjacent cells up, down, left, or right from his starting position.
Determine whether this is possible, and if so, output one valid sequence of moves with at most 5\times 10^6 moves between adjacent cells.
It can be proved that if a valid sequence of moves exists under the problem's conditions, then there exists one with at most 5\times 10^6 moves.
As long as the number of moves is at most 5\times 10^6, it is not necessary to minimize the number of moves.
Constraints
- 1 \leq H,W\leq 1000
- S_{i,j} is one of
#,.,o,x,S,G. - There is exactly one (i,j) satisfying S_{i,j}=
Sand exactly one satisfying S_{i,j}=G. - H and W are integers.
Input
The input is given from Standard Input in the following format:
H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}
Output
If it is impossible to reach the destination while satisfying the conditions, output No on the first line, and nothing on the second line.
If it is possible to reach the destination while satisfying the conditions, output Yes on the first line.
On the second line, output a string T representing a sequence of moves. T must satisfy all of the following conditions.
- The length \lvert T\rvert of T is between 1 and 5\times 10^6, inclusive.
- Each character of T is one of
U,D,L,R.- The i-th character of T being
U,D,L,Rmeans that in the i-th move after departing, Takahashi moves to the adjacent cell above, below, to the left, or to the right, respectively.
- The i-th character of T being
- For 1\leq i\leq \lvert T\rvert, Takahashi is not outside the grid after the i-th move.
- During the moves, the conditions of each cell are not violated.
- After the \lvert T\rvert-th move, Takahashi is at the destination cell. As long as this condition is satisfied, he may pass through the destination cell before the \lvert T\rvert-th move.
Sample Input 1
3 5 .#... .Sooo ..x.G
Sample Output 1
Yes DRUUDDRR
Let cell (i,j) denote the cell at the i-th row from the top and j-th column from the left.
Following the sample output, the path goes: cell (2,2) \to cell (3,2) \to cell (3,3) \to cell (2,3) \to cell (1,3) \to cell (2,3) \to cell (3,3) \to cell (3,4) \to cell (3,5), reaching the destination.
Other solutions such as DRUURLRRDD are also accepted.
On the other hand, since Takahashi cannot go straight through cell (3,3), solutions such as DRRR are not accepted.
Sample Input 2
3 3 #So xoG ..#
Sample Output 2
Yes DDLURR
Sample Input 3
2 2 So oG
Sample Output 3
No
It is impossible to reach the destination while satisfying the conditions.