No.2411 Reverse Directions
タグ : / 解いたユーザー数 65
作問者 : 👑



問題文
行 列のマス目があり,上から 番目,左から 番目のマスをマス と表します.いくつかのマスにはトゲが置かれています.
マス目の状態が文字列 で与えられます. が #
ならばマス にトゲがあり,.
ならばトゲがないことを表します.
マス目上に Alice がいます.Alice は,今いるマスと上下左右に隣接したマスへ移動を行うことが可能となります.
ただし,トゲのあるマスへの移動や,マス目の範囲外に出るような移動はできません.
Alice は,最初マス にいます.Alice の目標は,ちょうど 回の移動を行った後にマス にいるようにすることです(それより前の移動で,マス を通過してもよいです).
Alice は,何回目の移動でどの方向に移動するか(移動方法)をあらかじめ決めておき,それを Bob に伝えます.
さて,Alice が移動方法を Bob に伝える前,Alice がマス に到達するのを阻止したい Bob は,次のように宣言しました.
- 宣言内容: 回目の移動から 回目の移動までの Alice の移動の向きを,上下左右反転させる.具体的には,Alice が決めたその回の移動の向きが上,下,左,右の各向きの場合,その回はそれぞれ下,上,右,左の各向きに移動しなければならない.上下左右を反転した移動においても,トゲのあるマスやマス目の範囲外への移動は許されない.
ただし,Bob は宣言内容を必ずしも実行するとは限りません.そのため,Alice は,Bob が宣言内容を実行した場合でもしなかった場合でも,ちょうど 回の移動でマス に到達できるような移動方法を用いる必要があります.
そのような移動方法が存在するか判定し,存在する場合はひとつ示してください.
制約
- は整数である.
- は
.
または#
からなる長さ の文字列である. -
.
-
.
入力
入力は以下の形式で標準入力から与えられる.
出力
条件を満たす移動方法が存在しなければ,No
と出力せよ.存在するならば,次の形式で出力せよ.
Yes
ここで, は L
, R
, U
, D
からなる長さ の文字列であり, が L
, R
, U
, D
であることは, 回目の移動の向きがそれぞれ左,右,上,下であることを表す.
サンプル
サンプル1
入力
3 3 8 3 6 ..# ... #..
出力
Yes RDRDLUDR
Bob が宣言内容を実行した場合,Alice の移動方法は,RDLURDDR
となり,ちょうど 回でマス に到達できます.
一方,Bob が宣言内容を実行しなかった場合,Alice の移動方法は,RDRDLUDR
となり,同じくちょうど 回でマス に到達できます.
サンプル2
入力
4 4 2013 8 12 .... ..#. .... #...
出力
No
どのような移動方法をとっても,Alice はちょうど 回でマス に到達することはできません.
サンプル3
入力
4 4 14 7 8 .... ##.. ..## ....
出力
No
そもそも Alice はマス に到達することすらできません.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。