← 返回题目列表

AtCoder · stage0_2021_a

A. 巡逻

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

故事

为解决警员短缺问题,高桥市警察局决定引进无人巡逻车进行自动化巡逻。 无人巡逻车车顶配备了高分辨率全向摄像头,可以从当前位置直线看到整条道路。然后,它使用图像处理技术自动检测可疑活动。 为了给市民提供安全有保障的生活,我们希望设立一条巡逻路线,让巡逻车能够至少巡视一次城市的每个角落。 在这些巡逻路线中,请尽可能寻找短的路线。

问题陈述

您将获得一张地图,其中包括 N\times N 方块。 让 (0,0) 表示左上角的方块,并且 (i,j) 表示 i从顶部开始的第行和 j左起第 列。 每个方块要么是一个障碍物(#)或道路,您可以在道路方块上向上、向下、向左或向右移动。 每个道路方块包含一个数字 5-9,表示从相邻方格移动到该方格所需的时间。 我们定义一个道路广场 (i',j') 可见 (i,j) 当且仅当满足以下条件时:

  • i=i' 并且对于每个 j'' 与 \min(j,j')\leq j''\leq\max(j,j'), (i,j'') 是一个道路广场,或者
  • j=j' 并且对于每个 i'' 与 \min(i,i')\leq i''\leq\max(i,i'), (i'',j) 是一个道路广场。

例如,在下图中,灰色方块代表障碍物,白色和浅黄色方块代表道路,从绿色圆圈中可见的道路方块为浅黄色。

你的任务是找到从指定方块出发的路线 (si,sj),在道路方块上向上、向下、向左或向右移动,然后返回 (si,sj),使得所有道路方块至少可见一次。 路线越短,得分越高。 您可以在同一个广场上多次移动,甚至可以掉头。

评分

让 r 是道路方格总数, v 是至少一次可见的道路方块的数量,并且 t 是输出路线的总行程时间。然后你将获得以下分数。

  • If v<r, \mathrm{round}(10^4\times \frac{v}{r}).
  • If v=r, \mathrm{round}(10^4+10^7\times \frac{N}{t}).

如果输出非法(走出 N\times N 方格,在障碍方格上移动,或不返回 (si,sj)),会被判断为 WA。 有100个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。


输入

输入由标准输入按以下格式给出:

N si sj
c_0
\vdots
c_{N-1}
  • N 是介于 49 和 69,包括在内。
  • si, sj 是满足以下条件的整数 0\leq si\leq N-1 和 0\leq sj\leq N-1.
  • 每个 c_i 是一个长度正好的字符串 N 由字符组成 5, 6, 7, 8, 9,和 #。的 j- 第一个字符 ( 字符串的0\leq j\leq N-1) 代表正方形 (i,j) 如下。
    • # 表示该方块包含障碍物。可以保证 (si, sj) 不包含障碍物。
    • 5-9 表明该方块是一条道路,数字代表您从相邻方块移动到该方块所需的时间。

输出

让 U, D, L,和 R 代表运动 分别为 (i, j) to (i-1,j), (i+1,j), (i,j-1),和 (i,j+1)。 在一行中输出表示标准输出路径的字符串。

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 我们首先生成一个奇数 N=\mathrm{rand}(25, 35)\times 2 - 1 表示地图的大小和一个参数 K=\mathrm{rand}(2 N, 4 N) 代表道路数量。 从所有方块都是障碍物的初始地图开始,我们重复以下过程 K 次。

  1. 生成一个整数 d=\mathrm{rand}(0, 1) 代表道路的方向。
  2. 生成两个整数 i=\mathrm{rand}(0, (N-1)/2)\times 2 和 j=\mathrm{rand}(0, N-1) 代表道路的中心。
  3. 生成一个整数 h=\mathrm{rand}(3, 10) 代表道路的长度。
  4. 生成一个整数 w=\mathrm{rand}(5, 9) 代表行程时间。
  5. 对于每个 k 与 \max(j-h,0)\leq k\leq \min(j+h,N-1),我们覆盖正方形 (i,k) 当 d=0 或正方形 (k,i) 当 d=1 有路广场有出行时间 w.

重复之后,我们只保留道路方块中最大的连通分量,并用障碍物替换其余部分。 最后我们选择 (si,sj) 从道路方块中均匀随机。

工具


示例输入 1

49 32 20
597999666666666666#99999999999##5###########6####
5#7###6#############9#6###9#####5#8#########6####
5#7###6#6666666666666666669#####88888877777777777
5#7###6#########9###9#6###9#####5#8###5#####6####
5#7###6#########9##99969999988888889##5#####6####
5#7###6#########9###9#6###9#####5#8###5#####6####
5#7###6#6#######9###55555595555555899999888868888
5#7###6#6#8#####9###9#6###9#####5#8###5#####6####
7777777777777777777#9#6###9##8895989995999996####
5#7###6#6#8#6###9###9#6#####6###5#8###5#####6####
5#5#6#6#677777778888888888886###6#8##666666666###
6#5#6#6#6#8#6###6###5#6#####6###6#8###5#5###6####
6#5999696989699999#777777777777777777777999999999
6#5#6#6###8#6###6#####6#####6###6#8###5#5###6####
6#5#6#6###8868888###########676666666666666666666
6#5#6#6###8#6###6#9#########6###8#8#####5###6####
6#5#6#6555555555579777777777677787877777577777778
6#5#6#6###8#6###6#9#####5###6###8#8#####5#####6##
555555555555555666665677777777768#866666666666666
7#5#6#9###8#6###6#9#5###5#8#####8#8#######9###9##
7959699999896###9#9#5###5#8#####88888888889888988
7#5#6#9#5#8#6###9#9#5###5#8#####8#8#######9###9##
7#777797578777777797577#5#8#####8#########9###9##
7###9#9#5#8#####9#9#5###5#8#####8#8#######9###9##
7###9#5#5#8#####9#9#5###5#8#####8#8#######9###9##
7###9#5#5#8#####9#9#5#####8#####8#8#####8#9###9##
7###9999558555555555555555559999899#####8#9###9##
7###9#5#5#8#######8#5#####8#####8#8#####8#9###9##
688898685888######8#599999999999895###9#8#8###9##
6###9#6#5#########8#5#####8#####8#5#8#9#8#8###9##
67779777777777777788555555555555866686968666666##
6###9#6#5###8#8###8#5###8#8#####8#5#8#8#8#8###6##
6666966666698999998959999999##5#8#5#8#8#8#8###6##
6###9#6#####8#8###8#5###8#8###5#8#5#8#8#8#8#6#6##
6###9#6#####8#9#558575555#####5#8#5#8#8#8#8#6#6##
6###9#6#####8#9###8#7###8#####5###5#8#8#8###6#6##
6#6#9#6#####8#9#9#8#7#9#8#####5##9998989899969699
6#6#9#6#####8#9#9#8#7#9#8#####5###8#8#8#8###6####
6#7#9#6#55558595958#7#55855555555555858#####6####
##7#9#6#####8#9#9#8#7#9#8#####5###8#8#8#####6####
6#7888888888888888888888666###5#555555855555655##
6#7###6#####8#9#9#8#7#8#8#####7###8###8#####6####
6#7#855555558595999979999999997#####5#8#####6####
6#7#8#6#####8#7#9#8#7#8#######7#####5#8#####6####
6#7#8#6#####8#78988878888#####7#####5#8#####6#7##
6#7#8#######8#7#9#8#7#8#######7#####5#8#####6#7##
6#7#8#####8888789#8#7#87777777777777578777776#7##
6#7#8#######8#7#9#8#7#8#######7#####5#8#####6#7##
6979899995558575958575555555555555555555555565755

示例输出 1

UULLDDDDRRRRRRUULLLL