AT_rco_contest_2017_qual_b Food Collector

[problemUrl]: https://atcoder.jp/contests/rco-contest-2017-qual/tasks/rco_contest_2017_qual_b $ H $行$ W $列の正方形のマップがあります。マップの各マスは、障害物のあるマス・空マスのいずれかです。いくつかの空マスには高々1個のエサが置かれています。 最初の行を$ 1 $行目、最初の列を$ 1 $列目とします。 マップの$ sr $行$ sc $列目のマスに$ 1 $匹の犬がいます。犬は、開始から$ 0,1,2,… $秒後に、辺で隣接した障害物以外のマスに移動できます。犬の移動は瞬時に完了するものとします。 犬がエサのあるマスに移動すると、エサを**必ず獲得**します。エサを獲得すると、そのマスにあったエサは消え、あなたはエサに対応するスコアを得ます。 エサ$ i $のスコアの初期値は$ F_i $で、$ 1 $秒ごとに$ D_i $ずつ減少します。減少は犬が移動・獲得した直後に発生します。 犬の、開始から$ 0,1,2,…,K-1 $秒後の行動を出力して、スコアを最大化してください。

入力は以下の形式で標準入力から与えられます。入力はすべて整数です。 > $ H $ $ W $ $ K $ $ sr $ $ sc $ $ s_1 $ $ s_2 $ : $ s_H $ $ N $ $ fr_1 $ $ fc_1 $ $ F_1 $ $ D_1 $ $ fr_2 $ $ fc_2 $ $ F_2 $ $ D_2 $ : $ fr_N $ $ fc_N $ $ F_N $ $ D_N $ - $ H=W=50 $ - $ K=2500 $ - $ 1\leq\ sr\leq\ H $ - $ 1\leq\ sc\leq\ W $ - $ s_i\ (1\ \leq\ i\leq\ H) $ はマップの $ i $ 行目を表す長さ $ W $ の文字列であり、$ s_i $ を構成する文字は `#`, `.`のいずれかです。 - `#`は障害物マスを表します。 - `.`は空マスを表します。 - $ N $はエサの置かれるマスの個数を表します。 - $ 1\leq\ fr_i\ \leq\ H\ (1\leq\ i\leq\ N). $ - $ 1\leq\ fc_i\ \leq\ W\ (1\leq\ i\leq\ N). $ - $ 0\leq\ F_i\ \leq\ 10^5\ (1\leq\ i\leq\ N). $ - $ 0\leq\ D_i\ \leq\ 100\ (1\leq\ i\leq\ N). $ - $ fr_i,\ fc_i $ はエサの置かれるマスの行数, 列数を表します。 - $ F_i,\ D_i $ はエサのスコアの初期値, $ 1 $秒あたりの減少スコアを表します。 - $ (sr,\ sc),\ (fr_i,\ fc_i) $は互いに異なります。またこれらは必ず空マスの位置を指します。 - マップの端($ 1 $行目、$ H $行目、$ 1 $列目、$ W $列目)はすべて障害物マスです。 - 任意の空マスから、隣接する空マスのみを通って他の任意の空マスに行くことができます。

出力は以下の形式で標準出力に出力してください。 > $ movement $ - $ 1 $ 行目に **ちょうど**$ K $ 文字の文字列$ movement $を出力してください。 - $ movement $は犬の動作を表す文字列で、次のいずれかの文字からなります。 `U` 現在のマスより1行小さいマスに移動します。 `D` 現在のマスより1行大きいマスに移動します。 `L` 現在のマスより1列小さいマスに移動します。 `R` 現在のマスより1列大きいマスに移動します。 `-` 移動しません。

### 背景 わんわん！ ### ジェネレータとテスター ジェネレータとテスターを次のリンクから提供しています。 [ジェネレータ・テスター](https://gist.github.com/tomerun/e04223ea550b9ca7f1c5065430c29569) ### テストケースの生成 テストケースの生成は以下のようにして行います。"ランダムに選ぶ"と表記してあるものは、一様分布に従いランダムに選んでいるものとします。 1. $ H=W=50,\ K=2500 $とする。 2. $ H\times\ W $の`#`からなるマップを用意する。 3. $ step $を、$ [HW,\ 1.5HW] $の整数からランダムに選ぶ。 4. 座標$ (H/2+1,\ W/2+1) $と上下左右4方向からランダムに選んだ向き$ dir $を初期状態として、step回次を行う。 1. 現在の座標のセルを`.`に変える。 2. 確率$ 1/3 $で、`dir`に新しい向きをセットする。この向きは上下左右4方向からランダムに選ぶ。 3. `dir`の向きに移動する。 4. 現在の座標がマップの端($ 1 $行目、$ H $行目、$ 1 $列目、$ W $列目)にある場合、座標$ (H/2+1,\ W/2+1) $にワープする。 5. `.`となっているマスの中からランダムに$ (sr,sc) $を選ぶ。 6. $ N $を、$ [0.1R,\ 0.8R] $の整数からランダムに選ぶ。$ 0.1R,\ 0.8R $は小数点以下を切り捨てる。Rは、`.`となっているマスのうち$ (sr,sc) $でないものの個数である。 7. `.`となっているマスのうち$ (sr,sc) $でないものからランダムに、相異なる$ N $個のマスを選ぶ。これのそれぞれをエサを配置するマスとする。 8. 各エサの$ F_i $を、$ [0,10^5] $の整数からランダムに選ぶ。 9. 各エサの$ D_i $を、$ [0,100] $の整数からランダムに選ぶ。 ### ビジュアライザ 入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。 ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。 [ビジュアライザ](https://gist.github.com/tomerun/4472b99e33f4e9660fc230e738712013) ### Sample Explanation 1 注意: この入力はテストケースとしての制約を満たしていません。 開始時の位置を`S`, エサを$ 1,2 $で表したときのマップは以下のようになります。最終的に`X`の位置に移動します。 ``` ########## ###.....## ##2..##.1# #...####S# #..X###### #...###### #...###### #...###### #...###### ########## ``` - 開始から$ 0 $秒後にエサ$ 1 $を獲得し、$ 10 $秒後にエサ$ 2 $を獲得します。 - $ 2 $秒後にエサ$ 1 $の位置に戻ってきますが、エサ$ 1 $は消滅しているので何も起こりません。 - $ 16 $秒後以降の移動は壁があるマスの方に向かっていますが、移動しない扱いになっています。 - この出力によって得られるスコアは、以下のように計算されます。 - $ 0 $秒後にエサ$ 1 $を獲得したので、$ 10000-5\times\ 0=10000 $だけ獲得。 - $ 10 $秒後にエサ$ 2 $を獲得したので、$ 4-1\times\ 10=-6 $だけ獲得。 - 合計で$ 10000+(-6)=9994 $となり、これを$ 10000 $で割って小数点以下を切り上げ、$ 0 $との最大値をとって、$ 1 $が最終的なスコアになります。 ### Sample Explanation 2 ジェネレータに$ seed=1 $を指定することで同様の入力が得られます。