故事
AtCoder Inc.首席执行官高桥推出了多款最先进的打蜡机器人来改善办公环境。 他松了口气,以为办公室地板很快就会干净得闪闪发光,但很快就发现了严重的问题。 仅订购了一个操作机器人所需的控制器。
通常情况下,这将是一种绝望的情况,但幸运的是,控制器配备了先进的“按键配置”功能。 它是一种高性能设备,允许为每个机器人的每个按钮分配单独的操作。
高桥委托您解决这个难题。 他希望您利用有限的可用资源,有效地为整个办公室地板打蜡。
问题陈述
有一个 N \times N 代表办公室的网格。 左上角单元格的坐标是 (0, 0),以及单元格的坐标 i 向下行并 j 右侧的列是 (i, j)。 的周长 N \times N 网格被墙包围,相邻单元之间也可能有墙。
您要使用 M 机器人给所有细胞打蜡。 的初始位置 k第一个机器人是 (i_k, j_k),包括其初始位置,机器人访问的任何单元都被视为打蜡。
所有机器人均使用单个控制器同时操作。 该控制器有 K 按钮,在开始打蜡操作之前,您可以将每个按钮机器人对配置为执行五种可能的操作之一:移动到四个相邻单元格之一(上、下、左或右),或留在原地。 当按下按钮时,所有机器人同时执行为该按钮分配的各自动作。 机器人之间的按钮分配可能有所不同。例如,可以将控制器配置为“在按钮0上,机器人0向上移动,而机器人1向下移动”。 一旦打蜡开始,按钮分配就无法更改。
如果机器人尝试移动,但其当前单元格和目标单元格之间有一堵墙,它将保持在原地。 机器人之间互不干扰,多个机器人可以占据同一个单元。
您最多可以执行 2N^2 操作。 设计按钮分配和操作顺序,以便使用尽可能少的操作对所有单元格进行打蜡。
评分
让 T (T \leq 2N^2) 是输出操作序列的长度,令 R 是未打蜡细胞的数量。 您的分数计算如下。
- If R = 0, 3N^2 - T
- If R > 0, N^2 - R
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出。
N M K
i_0 j_0
\vdots
i_{M-1} j_{M-1}
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
- 在所有测试用例中, N=30, M=10,和 K=10.
- (i_k, j_k) 代表初始位置 k第一个机器人,并且所有初始位置都是不同的。
- 每行 v_{i,0} \cdots v_{i,N-2} 是长度为的二进制字符串 N-1。的 j- 第一个字符 v_{i,j} 表示是否有墙(
1)或不(0) 单元格之间 (i, j) 和细胞 (i, j+1). - 每行 h_{i,0} \cdots h_{i,N-1} 是长度为的二进制字符串 N。的 j- 第一个字符 h_{i,j} 表示是否有墙(
1)或不(0) 单元格之间 (i, j) 和细胞 (i+1, j). - 保证所有单元格相互可达。
输出
首先,将以下格式的按钮分配输出到标准输出。
c_{0,0} \cdots c_{0,M-1}
\vdots
c_{K-1,0} \cdots c_{K-1,M-1}
在这里, c_{i,j} 是一个单个字符,表示执行者所采取的操作 j第机器人当按钮时 按下 i 。它必须是以下 5 种类型之一:
U:上移一个单元格D:向下移动一个单元格L:向左移动一个单元格R:右移一个单元格S:留在原地
之后,按以下格式输出操作序列。
a_0
\vdots
a_{T-1}
在这里, a_t 是介于 0 和 K-1,代表打开时按下的按钮 t.
输入生成
让 \mathrm{rand}(L, U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
的初始位置 M 机器人通过统一选择确定 M 与 N^2 可能的细胞。
墙是通过重复以下过程 5 次来生成的。
- 从上、下、左或右中随机选择墙壁的方向。
- 确定墙长 L = \mathrm{rand}(10, 20).
- 对于垂直墙,选择起点 (i, j) by i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6).
如果选择 j 的绝对距离为 4 来自任何 j 用于先前生成的垂直墙,重做方向选择。
对于向上的墙壁,设置 v_{i-L+1, j}, \cdots, v_{i, j} to1。对于向下的墙,设置 v_{i, j}, \cdots, v_{i+L-1, j} to1。忽略任何超出范围的部分。 - 对于水平墙,选择起点 (i, j) by i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5).
如果选择 i 的绝对距离为 4 来自任何 i 用于先前生成的水平墙,重做方向选择。
对于左侧墙壁,设置 h_{i, j-L+1}, \cdots, h_{i, j} to1。对于右侧墙壁,设置 h_{i, j}, \cdots, h_{i, j+L-1} to1。忽略任何超出范围的部分。 - 生成墙后,检查所有单元格是否仍可相互可达。如果没有,重置墙并重新开始 5 次迭代。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 1
30 10 10 13 25 7 14 17 22 0 18 29 1 3 25 14 22 14 29 26 2 3 10 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 011111111111111111100000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 111111111110000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000
示例输出 1
L L L R U R S D L S R L L L D D L R D D D S R D D S U D U R L U S R D L S U L R L U U L L U D U D L L S U U S D L D U U D D D D U D S D U S U S U D S U L S D L D R R R L L L S L S L R S U S R D D R L 6 1 0 2 3 3 0 0 2 0 7 7 0 7 4 7 8 2 2 0