背景
汪汪!
問題文
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- 移动到当前位置后一列的格子。
-- 不移动。
发生器和测试仪
从以下链接提供生成器和测试器。
测试用例的生成
测试用例的生成如下所示。被标记为“随机选择”的,表示按照均匀分布随机选择。
- H=W=50, K=2500。
- H\times W可以得到第
#准备由……构成的地图。 - step,[HW, 1.5HW]从……的整数中随机选择。
- 座標(H/2+1, W/2+1)从上下左右四个方向随机选择的方向dir作为青少年状态,进行 step 次操作。
- 将当前坐标的单元格
.改变。 - 確率1/3在,
dir设置为新的方向。这个方向从上下左右四个方向中随机选择。 移动到 dir的方向。- 当前坐标位于地图的边缘(1行目、H行目、1列目、W列)时,坐标(H/2+1, W/2+1)。 从标记为
- 将当前坐标的单元格
.的格子中随机选择(sr,sc)。- N,[0.1R, 0.8R]从……的整数中随机选择。0.1R, 0.8R舍弃小数部分。R 是在标记为
.的格子中,不是(sr,sc)的格子的数量。 从不是 .的格子中,不是(sr,sc)的格子中随机选择相异的N个格子。将每个格子作为放置饵料的格子。- 各个食物的F_i,[0,10^5]从……的整数中随机选择。
- 各个食物的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 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
- 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。
还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。