問題一覧 > 通常問題

No.2411 Reverse Directions

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 65
作問者 : 👑 AngrySadEight / テスター : hamamu hari64 hari64
2 ProblemId : 9896 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-31 01:05:58

問題文

HHWW 列のマス目があり,上から ii 番目,左から jj 番目のマスをマス (i,j)(i, j) と表します.いくつかのマスにはトゲが置かれています.

マス目の状態が文字列 S1,S2,,SHS_1, S_2, \dots, S_H で与えられます.Si,jS_{i, j}# ならばマス (i,j)(i, j) にトゲがあり,. ならばトゲがないことを表します.

マス目上に Alice がいます.Alice は,今いるマスと上下左右に隣接したマスへ移動を行うことが可能となります.

ただし,トゲのあるマスへの移動や,マス目の範囲外に出るような移動はできません.

Alice は,最初マス (1,1)(1,1) にいます.Alice の目標は,ちょうど KKの移動を行った後にマス (H,W)(H, W) にいるようにすることです(それより前の移動で,マス (H,W)(H, W) を通過してもよいです).

Alice は,何回目の移動でどの方向に移動するか(移動方法)をあらかじめ決めておき,それを Bob に伝えます.

さて,Alice が移動方法を Bob に伝える前,Alice がマス (H,W)(H, W) に到達するのを阻止したい Bob は,次のように宣言しました.

  • 宣言内容LL 回目の移動から RR 回目の移動までの Alice の移動の向きを,上下左右反転させる.具体的には,Alice が決めたその回の移動の向きが上,下,左,右の各向きの場合,その回はそれぞれ下,上,右,左の各向きに移動しなければならない.上下左右を反転した移動においても,トゲのあるマスやマス目の範囲外への移動は許されない.

ただし,Bob は宣言内容を必ずしも実行するとは限りません.そのため,Alice は,Bob が宣言内容を実行した場合でもしなかった場合でも,ちょうど KK 回の移動でマス (H,W)(H, W) に到達できるような移動方法を用いる必要があります.

そのような移動方法が存在するか判定し,存在する場合はひとつ示してください.

制約

  • H,W,K,L,RH, W, K, L, R は整数である.
  • 3H,W5003 \leq H, W \leq 500
  • 4K5×1054 \leq K \leq 5 \times 10^5
  • 1LRK1 \leq L \leq R \leq K
  • SiS_i. または # からなる長さ WW の文字列である.
  • S1,1=S_{1,1} = .
  • SH,W=S_{H,W} = .

入力

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

HH WW KK LL RR
S1S_1
S2S_2
\vdots
SHS_H

出力

条件を満たす移動方法が存在しなければ,No と出力せよ.存在するならば,次の形式で出力せよ.

Yes
TT

ここで,TTL, R, U, D からなる長さ KK の文字列であり,TiT_iL, R, U, D であることは,ii 回目の移動の向きがそれぞれ左,右,上,下であることを表す.

サンプル

サンプル1
入力
3 3 8 3 6
..#
...
#..
出力
Yes
RDRDLUDR

Bob が宣言内容を実行した場合,Alice の移動方法は,RDLURDDR となり,ちょうど 88 回でマス (3,3)(3, 3) に到達できます.

一方,Bob が宣言内容を実行しなかった場合,Alice の移動方法は,RDRDLUDR となり,同じくちょうど 88 回でマス (3,3)(3, 3) に到達できます.

サンプル2
入力
4 4 2013 8 12
....
..#.
....
#...
出力
No

どのような移動方法をとっても,Alice はちょうど 20132013 回でマス (4,4)(4, 4) に到達することはできません.

サンプル3
入力
4 4 14 7 8
....
##..
..##
....
出力
No

そもそも Alice はマス (4,4)(4, 4) に到達することすらできません.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。