故事
为解决警员短缺问题,高桥市警察局决定引进无人巡逻车进行自动化巡逻。 无人巡逻车车顶配备了高分辨率全向摄像头,可以从当前位置直线看到整条道路。然后,它使用图像处理技术自动检测可疑活动。 为了给市民提供安全有保障的生活,我们希望设立一条巡逻路线,让巡逻车能够至少巡视一次城市的每个角落。 在这些巡逻路线中,请尽可能寻找短的路线。
问题陈述
您将获得一张地图,其中包括 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 次。
- 生成一个整数 d=\mathrm{rand}(0, 1) 代表道路的方向。
- 生成两个整数 i=\mathrm{rand}(0, (N-1)/2)\times 2 和 j=\mathrm{rand}(0, N-1) 代表道路的中心。
- 生成一个整数 h=\mathrm{rand}(3, 10) 代表道路的长度。
- 生成一个整数 w=\mathrm{rand}(5, 9) 代表行程时间。
- 对于每个 k 与 \max(j-h,0)\leq k\leq \min(j+h,N-1),我们覆盖正方形 (i,k) 当 d=0 或正方形 (k,i) 当 d=1 有路广场有出行时间 w.
重复之后,我们只保留道路方块中最大的连通分量,并用障碍物替换其余部分。 最后我们选择 (si,sj) 从道路方块中均匀随机。
工具
- 输入:用于本地测试的一组 100 个输入(种子 0-99),包括样本输入(种子 0)。这些输入与实际测试用例不同。
- 网络上的可视化工具
- 输入生成器和可视化工具:如果您想使用更多输入,或者如果您想在本地可视化输出,您可以使用此程序。你需要一个编译环境 Rust 语言.
示例输入 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