/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
問題文
人気ゲーム実況者として活動しているXは、新しい動画の制作に取り組んでいます。今回は、とあるパズルゲームを攻略することにしました。
このゲームの目的は、 H行W列のマスからなるマップの中で、プレイヤーを動かしてできるだけ多くのコインを集めることです。詳しいルールは以下の通りです。なお、マップの一番上の行を 0 行目、一番左の列を 0 列目とします。
- マップの各マスは、壁のマス・コインのマス・罠のマス・空のマスのいずれかである
- マップの外周（0行目・H-1行目・0列目・W-1列目）は壁のマスである
- 初期状態では空のマスが1つだけあり、そこにプレイヤーがいる
- 1回のコマンドで、プレイヤーを上下左右いずれかの隣接したマスへ移動させることができる
- 移動先が壁のマスだった場合、移動せず現在のマスにとどまる
- プレイヤーがコインのマスに入った場合、コインを得る。そのマスからコインはなくなり、空のマスになる
- プレイヤーが罠のマスに入った場合、それ以降プレイヤーは移動できなくなる
- コマンドは最大 T 回与えることができる
このゲーム内には N 個のマップが用意されています。ただ高得点を取るだけでは面白くないと考えたXは、次のチャレンジをすることにしました。
- N 個のマップの中から K 個のマップを選ぶ
- それら K 個のマップを、同一のコマンドで操作する
マップの選び方と実行するコマンドを決め、得られるコインの数の合計を最大化してください。
各テストケースの得点および、この問題の得点は、次のように計算されます。
- 1つのテストケースの得点は、選んだ K 個のマップで得られたコインの数の合計です。
- テストケースは全部で 30 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N K H W T
row_{0,0}
row_{0,1}
:
row_{0,H-1}
row_{1,0}
:
row_{N-1,H-1}
- N はマップの数を表す整数で、N=100 を満たします。
- K は使用するマップの数を表す整数で、K=8 を満たします。
- H はマップの行数を表す整数で、H=50 を満たします。
- W はマップの列数を表す整数で、W=50 を満たします。
- T はコマンドの回数の最大値を表す整数で、T=2,500 を満たします。
- row_{i,j} は i 番目のマップの j 行目を表す W 文字の文字列です。各文字は、
#,o,x,@のいずれかです。#は壁のマスを表します。oはコインのマスを表します。xは罠のマスを表します。@はプレイヤーがいるマスを表します。- 各マップの外周は
#であることが保証されます。 - 各マップに
@はただ一つ存在することが保証されます。
出力
1行目に、選択したマップの番号（0始まり）を表す整数を K 個、スペース区切りで出力してください。
2行目に、実行するコマンド列を表す T 文字以下の文字列を出力してください。
M_0 M_1 … M_{K-1}
commands
- M_0, M_1, …, M_{K-1} は、互いに異なる 0 以上 N 未満の整数です。
- commands の i 文字目は、i 個目のコマンドを表します。
- 各コマンドは、以下の文字によって表されます。
U- 現在のマスより1行小さいマスに移動します。（上に移動します）
D- 現在のマスより1行大きいマスに移動します。（下に移動します）
L- 現在のマスより1列小さいマスに移動します。（左に移動します）
R- 現在のマスより1列大きいマスに移動します。（右に移動します）
テストケースの生成について
各マップは次の手順で生成されます。
- 外周を壁のマスにする
- 外周以外のマスを、それぞれ確率 0.77 でコインのマスに、確率 0.20 で壁のマスに、確率 0.03 で罠のマスにする
- 外周以外のマスを1つ選び、空のマス（初期状態でプレイヤーがいるマス）に置き換える
入力例1
4 2 8 8 3 ######## #o#oooo# #ooooo## ##ooooo# #oooo#x# ##o#ooo# ##@ooox# ######## ######## ##xoooo# #oo#oox# #oooooo# #oooxoo# ##o@o#o# #o#oo#o# ######## ######## #ooo##o# #oo##oo# #ooo@oo# ###oooo# #o#xo#o# #ooooo## ######## ######## #ooo#oo# ##oooo## ##ooo#@# #oooooo# #oo#ooo# #oooo#x# ########
注意: この入力はテストケースとしての制約を満たしていません。
マップを以下に図示します。
出力例1
1 2 URR
マップ1とマップ2を選びました。全てのコマンドを実行後のマップの様子は以下のようになります。
- 1つめのコマンドでは、マップ1のプレイヤーは上に移動してコインを得ます。マップ2のプレイヤーは、上が壁のマスのため移動しません。
- 2つめのコマンドでは、マップ1のプレイヤーは右に移動して罠のマスに入ります。マップ2のプレイヤーは、右に移動してコインを得ます。
- 3つめのコマンドでは、マップ1のプレイヤーは罠のマスに入っているため移動できません。マップ2のプレイヤーは、右に移動してコインを得ます。
- マップ1で1個、マップ2で2個のコインを得たため、このテストケースで得られるスコアは、3点です。
ジェネレータとテスター
テストケースジェネレータとテスターを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。