← 返回题目列表

AtCoder · rco_contest_2017_qual_b

B. 食物收藏家

中文机器翻译题面 查看原题

背景

汪汪!


問題文

H行W栏中有一张骡子的地图。 每张地图要么是障碍物,要么是空障碍。 有些空地最多只放一个诱饵。

第一句1行,第一个列为1列。地图的sr行sc列的格子上有1只狗。狗从开始后0,1,2,…秒起,可以移动到与边邻接且没有障碍物的格子上。狗的移动被视为瞬间完成。当狗移动到有食物的格子时,必定可以获得。。获得饲料后,该格子上的饲料会消失,你将获得对应饲料的 su 颗数。 饲料i的核心少年的值每F_i在,1秒减少D_i。减少在狗移动或获得后立即发生。

从开始算起0,1,2,…,K-1秒后的狗的行动输出,以最大化 suk oa。


入力

输入以以下格式从标准输入给出。输入全都是整数。

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
    移动到当前位置上一行的格子。
    D
    移动到当前位置下一行的格子。
    L
    移动到当前位置前一列的格子。
    R
    移动到当前位置后一列的格子。
    -
    不移动。

发生器和测试仪

从以下链接提供生成器和测试器。

发电机测试仪


测试用例的生成

测试用例的生成如下所示。被标记为“随机选择”的,表示按照均匀分布随机选择。

  1. H=W=50, K=2500。
  2. H\times W可以得到第#准备由……构成的地图。
  3. step,[HW, 1.5HW]从……的整数中随机选择。
  4. 座標(H/2+1, W/2+1)从上下左右四个方向随机选择的方向dir作为青少年状态,进行 step 次操作。
    1. 将当前坐标的单元格.改变。
    2. 確率1/3在,dir设置为新的方向。这个方向从上下左右四个方向中随机选择。 移动到
    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 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。

展示台

观察仪主体