AT_stage0_2021_a.Patrolling

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个大小为 $N \times N$ 的地图。其中左上角的格子为 $(0, 0)$ ，向下移动 $i$ 次、向右移动 $j$ 次到达的格子记为 $(i, j)$ 。每个格子要么是障碍物（用 # 表示），要么是道路（用数字 5 至 9 表示）。道路上的数字表示进入该格子需要的时间，且可以在道路上进行上下左右的移动。

定义位于 $(i, j)$ 的道路格子时，如果 $(i', j')$ 满足以下条件之一，则称其在“视线内”：

$i = i'$ 并且从 $\min(j, j')$ 到 $\max(j, j')$ 的所有格子都是道路；
$j = j'$ 并且从 $\min(i, i')$ 到 $\max(i, i')$ 的所有格子都是道路。

例如，下图中灰色格子为障碍物，白色和浅黄色格子为道路，绿色圆圈所在位置能看到的所有道路格子都用浅黄色表示。

从指定道路格子 $(si, sj)$ 出发，找到一条巡回路线，可以在上下左右移动，最终回到起点 $(si, sj)$ 。要求这条路线能让所有道路格子至少进入过视线一次，并且整体用时最短。允许在同一格子多次经过，也可以进行掉头。

输入格式

输入为以下格式：

$N\ si\ sj\ c_0\ \ldots\ c_{N-1}$

$N$ 为 49 到 69 之间的奇数。
$si, sj$ 是满足 $0 \leq si, sj < N$ 的整数。
每个 $c_i$ $c_{i}$ 是由字符 5, 6, 7, 8, 9 和 # 组成的长度为 $N$ $N$ 的字符串，第 $j$ $j$ 个字符表示位置 $(i, j)$ $(i, j)$ 的格子信息：
- # 表示障碍物，保证 $(si, sj)$ 的位置不是障碍物。
- 5 到 9 表示该格子是道路，数字表示进入需要的时间。

输出格式

输出一个字符串，描述从起点出发的巡回路线。移动到上、下、左、右分别用 U, D, L, R 表示，并且路线需要在一行中输出。

输入输出样例

输入#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

说明/提示

得分规则

假设所有道路格子数为 $r$ ，至少被看到一次的道路格子数为 $v$ ，巡回路线的总时间为 $t$ ，则得分计算如下：

如果 $v < r$ ，得分是 $\mathrm{round}(10^4 \times \frac{v}{r})$ 。
如果 $v = r$ ，得分为 $\mathrm{round}(10^4 + 10^7 \times \frac{N}{t})$ 。

若输出路线不合法，如超出地图范围，移动到障碍物或最终未回到起点 $(si, sj)$ ，则判定为 WA。总共有 100 个测试用例，所有测试用例的得分相加为提交的总得分。如果任何一个测试用例没能通过，则成绩为 0 分。最终排名由最高得分决定，若得分相同则按提交时间的早晚排序。

输入生成方法

用 $\mathrm{rand}(L, U)$ 表示生成 $L$ 到 $U$ 之间的随机整数。首先生成地图大小 $N = \mathrm{rand}(25, 35) \times 2 - 1$ ，以及道路数量 $K = \mathrm{rand}(2N, 4N)$ 。从所有格子都是障碍物的状态开始，执行以下操作 $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)$ 。
对于任意 $\max(j-h, 0) \leq k \leq \min(j+h, N-1)$ ，用移动时间 $w$ 的道路格子覆盖格子 $(i, k)$ 如果 $d=0$ ，或覆盖格子 $(k, i)$ 如果 $d=1$ 。

最后，仅保留最大连通的道路部分，其余部分变为障碍物，并从道路格子中随机选择一个作为起点 $(si, sj)$ 。

工具

输入数据：用于本地测试的 100 个输入数据（seed 0-99），不与实际测试用例相同。
Web 版可视化工具
输入生成器和可视化工具：用以生成更多输入的输入生成器和本地可视化工具。需先安装 Rust 语言编译环境。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页