B - Food Collector 解説 /

実行時間制限: 10 sec / メモリ制限: 1024 MB

背景

わんわん！

問題文

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列大きいマスに移動します。
    -
    移動しません。

ジェネレータとテスター

ジェネレータとテスターを次のリンクから提供しています。

ジェネレータ・テスター

テストケースの生成

テストケースの生成は以下のようにして行います。"ランダムに選ぶ"と表記してあるものは、一様分布に従いランダムに選んでいるものとします。

  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]の整数からランダムに選ぶ。

入力例1

10 10 20 4 9
##########
###.....##
##...##..#
#...####.#
#...######
#...######
#...######
#...######
#...######
##########
2
3 9 10000 5
3 3 4 1

注意: この入力はテストケースとしての制約を満たしていません。

出力例1

ULRLULLLDLL-DDR-RRRR

開始時の位置を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が最終的なスコアになります。

入力例2

50 50 2500 23 16
##################################################
###......#########.#.###.##.###.################.#
########.#########.#.###.##.###.################.#
########.#.....###.#........###.################.#
########.##.##.###................##############.#
###...................##.######.#.##############.#
###########.###.#..#..##.######.#.##############.#
###########.#...#..#...............#############.#
###########.#.#...............#.....##...........#
###########.###.#.#.#..#......#....###.###########
###########.#####.#.##.#........#..###.###########
###########.####................#..###.###########
###########.####....#........#..#.........########
#########...............................##########
##.######.######...................###..##########
#..######.#................#.#......##..##########
#..######.#..#.#........................##########
#.........................#..#......#...##########
#..........#..............#..#......#...##########
#..........#.....#......................##########
#...#..#...#.................#......#...##########
#..##..#.#.#........................#...##########
#..........##.......................#....#########
##.#.#.#.#.#...................#....#.......######
####.#.........................#....#...###.######
####.....................................##.######
####.........##.....#..........#..#.##...##.######
####.......................#......#.#.......######
#.##......##.#....................#.#....#########
#...................................#....#########
#.##.##...##.##.#........................#########
#.##.##...##.##.....................#....#########
#.##..................#.............#...##########
#....##....#........................#...##########
#...................................#...##########
#.......................................##########
##.#..##....###.##.#....................##########
####..##..#.###.##.#.##...#........#.#..##########
####..##..#.###.##.#.##...#.............##########
###.......#........#.##...#.#...####.#.###########
####..##..#####.####.##...#.#...#.........########
####..##..#####.####.##...#.#...#.####.##.########
####..##..#####.####......#.....#.###.....########
#####.###.#####.####..#.#.............###.########
#####.###.#####..###..####.##.#.#.#######.########
#####.###.#####..###..####.##.#.#.################
#.....###.####....##..####.#......################
#########..................##.......##############
####################.#..........#.################
##################################################
128
36 6 33421 59
28 14 59990 74
21 15 91235 96
35 21 27683 71
20 11 11576 6
30 18 1583 87
6 4 21368 56
9 16 96637 100
26 11 21283 33
31 8 20294 33
2 21 65091 29
19 22 18039 17
5 33 98990 34
24 18 6500 60
14 10 26823 20
25 28 85792 28
47 18 537 36
26 23 60156 38
28 15 17810 17
20 39 28088 77
33 31 49621 37
20 32 83255 24
4 49 17499 96
31 9 93800 85
18 35 75782 37
24 25 61216 36
23 35 11322 33
6 5 84247 43
12 26 97308 40
6 6 7020 93
25 44 48412 4
6 15 30741 93
28 40 60392 6
23 28 50081 46
5 27 27989 38
23 32 91705 72
12 23 26710 59
28 17 36863 94
20 36 12665 77
17 12 69103 43
19 2 22817 20
18 38 27069 40
10 25 89918 76
32 28 7871 14
35 24 40156 17
32 16 50330 35
35 16 94626 5
17 33 2103 94
48 34 87848 82
19 21 52841 86
2 9 47976 39
46 17 10653 70
4 15 28399 40
5 30 85741 4
16 20 66310 36
13 27 79008 52
25 13 53822 71
8 18 96550 51
39 34 29271 54
38 24 92830 30
38 34 90137 86
48 18 82174 6
24 9 96186 3
7 18 21405 19
16 23 53528 2
31 31 8980 90
23 14 6256 21
49 24 57192 21
30 38 29651 33
16 24 80144 66
39 19 71496 10
26 38 22365 82
16 27 94591 4
30 19 13375 52
48 22 13906 29
45 21 15200 100
17 24 73814 1
5 15 89249 49
43 31 12710 19
16 21 89488 33
17 29 70865 55
33 20 71412 100
19 40 96591 32
8 30 6866 40
34 3 68501 20
24 28 99184 74
31 38 60999 70
8 22 88203 87
21 19 55945 64
14 18 46530 68
33 27 90347 100
44 31 40042 4
8 16 25939 91
44 28 17446 7
43 32 30346 61
22 2 16138 39
17 32 23668 8
20 29 3455 11
21 38 10036 59
14 19 80874 52
24 23 25439 55
29 8 7661 89
32 26 86161 51
22 27 18200 72
40 10 13922 31
8 23 58303 73
24 40 57936 38
27 11 14252 62
37 19 18676 93
17 21 46494 63
20 14 87223 9
39 39 9764 8
20 3 74043 69
47 16 76510 86
20 31 74695 46
29 26 78237 53
28 13 12037 81
38 19 65664 100
40 13 62357 39
27 13 95311 27
34 13 2537 69
46 6 94570 43
23 5 65255 8
2 25 93842 49
18 28 29560 48
12 24 60028 98
36 30 40774 28
24 42 57689 22

ジェネレータにseed=1を指定することで同様の入力が得られます。

出力例2

LDUDURRLDLRURDLURRU-DR--RRURDLRDRDRUULUDRRUDDD-DLLDRDLRD-R-UU-R--L-ULURDU-DULRL-RUDUUR-URUURUD-RDLLLRRDUURLDURLD-R-LDLURUULRULRLDUURLRDLDLUULLLU-DL-DLD-U-DLLURDR-RUD-URRUDLU-RUU-URUDL-DLLUDRUUURUU--RRL-DR-RDUUUULURDRU--UDLLRLDRU-DLLU-DDLLUD-RRDRLD-UDDRDDUUDLUR--D-L-RUUUDR--LL-LUURLUD--UDRDDL--UDL-RRR-L-LRUDUDD----D-DRDLU-UU-RRD-DL-RR-LDDR-UDRRRUU-DDR-U-L-UDUULRDRDLLUD--D--LRUU-UUULU-DDDDLDRUDLDRURUURLDRL-L-RRDRD-LL-D-LD--RDRLDULLLD-L-L-URRURLURL-L--DR--RD-LLULRUDRLLUDDRUUDD-URLRRRLUD-URLD-UDDUURLLUUR-LDULDRRDRD-LD-LRL-R-D-DLDRDD-LLLLDDDULL--LLDDLU--DU---LLDRUL--LDD-UL-L-ULUDUDDULD-R-LUR-LDDDRDL-LULLULLDUULU-DRRU--DDUUDLDRU-U--UUURDD-----URDLUDRDULU-L-U-D-LUUURRLUDD-R-UL-DUD-LLRRUULRU-D-R-L--RDRLLLRLDUDDLU--DULLD-LLLLDRUUURURRR-RDUDLUD--U-R-ULRLR-UL-U-RDDRRRRRLR-RURRUD--UUDRULDLRLURLD-R-RL-ULLL-DLRDD-U-DUR-L--DU-DLDR-RLRL-LLDLRDRU-LRLDDRD-U-L-RRD---ULD-RRDULLURL-RLDUR-DD-DLRDU---LUDRR-L-U-U--UD-UD--URUR--LUD-DUDR--URLD-DD---DU-RRUUUULLDUL-L-UUDUDDRURLRU-R-DR-DLUDRL--LRLDDL---DDULLUUUDLRUUDLRDUULDURRULURUL-DRDULDDR---U-URDRRUURLR-L-LDRLURR-R-UU-R-URDRD-U-RLLDD--L-RD-DRRRRU-L-LRR-UDLURLULRLRRDUDRL-RDLD-URRL-L-DURLU-UDDDLLLLLDUUU-ULUURRUR-UU-RDD--URL-UDDDDU-DULURUURD-DUL-LR--ULDLL-DLD--RULD-DUULRUDLD-DLDRL-DU--R-RRDDDRLRD-LDDRRR-R-RDDUULL-DRDUDLL-RDL--UUUUDLRR-L-RDRDRD-UDRUR--DLULURR-UD-LLRLRDL-LR-DUUUDLDD-ULURLRR--R--UDUDUDLDR-RUD-DRU-DDRLR--U-LLD-RDU-U-RRULDLUDRDUL-RDUULD-R--LRRRLULDD--UUU-D-RLDD-LLULL-L--R--LRDR-RRD-U-LUUURRRD--R-URRDU-RRRULURUR-RLULLL-UUUURLLDR--RLLDU-RRUL-DR-LURUDDURL-DRDR-R-UULDLR-RDURD---LLRUULLUDDRULLRRRRUURDDD-DLUDRURLLUDLLRL-DDR--L-URLRU--UR-LDRUURUDDU-DUD-UDDLL-RU-R-DDLDURLRUULULDURR-RRRDRUUDDRLRLLDDDULULRU--DRRLRRDL--ULLRRRLDUULULR-URULLLRDURR-LU-LURLUDLUURU-RU--D-DD-RD-LLRRU-RDUUR-RRDDRLDD---LLRRLL-LDDUUR-ULRUDRLRULDLDUDU-ULLLL--LRRUDDDDRLL-RDRUR-UULDDUL-L--DLLLDU-UDDULUR--D-LDDRDUU-L---RDRULRU-DDLRRLRU-URDRUURR-DD-RURULL-LLDL-DDRULLULL--LRURLUL--D-D-DDLUURUDUDURUL-DDDRLRDUU-RD-UU-URRL-RULDU-R--ULLRURRDRLLDLL-D-LUL-D-UULRU-DUUDLDULUL-DRRRRLRDRURDDRUU-RD--UDRUULLLL-L-RLDRRUD-ULRLURDD-LLDDLL--URLUUDULUDLUDR--DLDDLLLRRURLD-R--DR-U-U-LURUURDD-RRU--LDRLUUDLRUUUULRRRU-LULDD-UDULDLUU---D-LUUDRR-U-ULUU-LL-R-URLLD-RDRRUL-LLRU-R--DUDDU-R--RRULLUU-DRRLDLDDRUR--UD-R-DRDDL-LDRDLRRDUDUUDRDLU--D--RRD-DULR-R--ULUU-DRLUULLR-UD-LRL-LULRRDDU-LUDUDU-UR--R-RLLLULDD-L-URRDDDULDUU-RURUDLUUDUURDDDR-LRL--R-L-DU-DDD-DURDRRLDLLL-UULL-RLRRL--URUUL-RDR-RDLDDLDURRLDLDUUD-ULU-DR--RLR-LRDLRDDRLUL-RUR-U--URU-D-LD--RRURRRR-UDLU--LLRDDUDL---DUURRDUD-RUD-UURDLLD-RLD

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

  • このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
  • このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
  • このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ