AT_stage0_2021_a Patrolling

给定一个大小为 $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$ 是由字符 `5`, `6`, `7`, `8`, `9` 和 `#` 组成的长度为 $N$ 的字符串，第 $j$ 个字符表示位置 $(i, j)$ 的格子信息： - `#` 表示障碍物，保证 $(si, sj)$ 的位置不是障碍物。 - `5` 到 `9` 表示该格子是道路，数字表示进入需要的时间。

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

### 得分规则 假设所有道路格子数为 $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$ 次： 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. 对于任意 $\max(j-h, 0) \leq k \leq \min(j+h, N-1)$，用移动时间 $w$ 的道路格子覆盖格子 $(i, k)$ 如果 $d=0$，或覆盖格子 $(k, i)$ 如果 $d=1$。 最后，仅保留最大连通的道路部分，其余部分变为障碍物，并从道路格子中随机选择一个作为起点 $(si, sj)$。 ### 工具 - [输入数据](https://img.atcoder.jp/ahc005/c746dac8cc11fd18c68063546997666e.zip)：用于本地测试的 100 个输入数据（seed 0-99），不与实际测试用例相同。 - [Web 版可视化工具](https://img.atcoder.jp/ahc005/dc9ed10f037e2dd4b48ca255dbd470d9.html) - [输入生成器和可视化工具](https://img.atcoder.jp/ahc005/dc9ed10f037e2dd4b48ca255dbd470d9.zip)：用以生成更多输入的输入生成器和本地可视化工具。需先安装 Rust 语言编译环境。 **本翻译由 AI 自动生成**