【AtCoder ABC452D】Go Straight

by

関連記事

1. D – Go Straight

縦 HH マス × 横 WW マスのマス目があり、高橋君はこのマス目を上下左右に移動します。
上から ii 番目かつ左から jj 番目 (1≤i≤H, 1≤j≤W)(1 \le i \le H,\ 1 \le j \le W) のマスの状態は文字 Si,jS_{i,j} で表されます。
Si,jS_{i,j} は #, ., o, x, S, G のいずれかです。

  • Si,jS_{i,j} = # のとき、このマスに立ち入ることはできない。
  • Si,j=.S_{i,j} = . のとき、このマスに自由に出入りすることができる。すなわち、このマスに立ち入った後、上下左右に隣接する好きなマスに（存在するならば）移動できる。
  • Si,j=oS_{i,j} = o のとき、このマスでは直前の移動と同じ方向に移動しなければならない。すなわち、このマスに立ち入った後は、方向を変えずに次のマスへ移動しなければならない。
  • Si,j=xS_{i,j} = x のとき、このマスでは直前の移動と同じ方向に移動することはできない。すなわち、このマスに立ち入った後は、必ず方向を変えて次のマスへ移動しなければならない。なお、180180 度方向を変えて元のマスに戻ることは方向を変えて移動することに含まれる。
  • Si,j=SS_{i,j} = S のとき、このマスは高橋君が最初にいる地点である。このマスは自由に出入りすることができる。
  • Si,j=GS_{i,j} = G のとき、このマスは高橋君の目的地である。このマスは自由に出入りすることができる。

なお、Si,j=S,GS_{i,j} = S, G であるような (i,j)(i,j) は、1≤i≤H, 1≤j≤W1 \le i \le H,\ 1 \le j \le W の範囲にちょうど 11 つずつ存在します。

高橋君は最初にいる地点から、上下左右に隣接するマスへの移動を繰り返して、目的地へと到達したいです。
そのようなことが可能か判定し、可能ならば条件をみたす移動方法であって、隣接するマスへの移動回数が 5×1065 \times 10^6 以下であるようなものを一つ出力してください。

なお、問題の条件下において条件をみたす移動が可能ならば、そのような方法であって移動回数が 5×1065 \times 10^6 以下であるようなものが存在することが証明できます。
また、移動回数が 5×1065 \times 10^6 以下である限り、回数を最小化する必要はありません。

  • 1≤H,W≤10001 \le H, W \le 1000
  • Si,jS_{i,j} は #, ., o, x, S, G のいずれかである。
  • Si,j=S,GS_{i,j} = S, G となる (i,j)(i,j) がちょうど一つずつ存在する。
  • H,WH, W は整数

入力は以下の形式で標準入力から与えられる。

H W H\ W S1,1S1,2…S1,W S_{1,1}S_{1,2}\ldots S_{1,W} S2,1S2,2…S2,W S_{2,1}S_{2,2}\ldots S_{2,W} ⋮ \vdots SH,1SH,2…SH,W S_{H,1}S_{H,2}\ldots S_{H,W}

条件をみたすように移動することが不可能ならば、1 行目に No を出力し、2 行目には何も出力してはならない。

条件をみたすように移動することが可能ならば、1 行目に Yes を出力せよ。
2 行目には移動方法を表す文字列 TT を出力せよ。

TT は次の条件をすべてみたす必要がある。

  • |T||T| は 11 以上 5×1065 \times 10^6 以下である。
  • TT の各文字は U, D, L, R のいずれかである。
  • TT の ii 文字目が U・D・L・R であることはそれぞれ、高橋君が出発してから ii 回目の移動で上・下・左・右に隣接するマスに移動することを表す。
  • 1≤i≤|T|1 \le i \le |T| について、ii 回目の移動の後で高橋君がマス目の外に出ることはない。
  • 移動の途中で各マスの条件に違反しない。
  • |T||T| 回目の移動の後で、高橋君は目的地のマスにいる。なお、この条件を満たしている限り、|T||T| 回目の移動より前に目的地のマスを通り過ぎていても良い。

1.1. 例 1

3 5
.#...
.Sooo
..x.GCode language: CSS (css)

出力例

Yes
DRUUDDRR

上から (i) 番目かつ左から (j) 番目のマスをマス ((i,j)) で表します。