← 返回题目列表

AtCoder · rcl_contest_2020_final_b

B. 超级清洁机器人

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

問題文

N 行 N 列的网格。从上面 i 行,从左开始 j 列单元格 表示为 (i, j) 。

在每个单元格上方, 有一张纸,上面写着A减去Z为止的字母。 此外,网格的一个单元格内有一个球形清洁机器人X,其他单元格内有一个球形清洁机器人X。 P 单元格有列。

您移动支柱并上下左右滚动机器人,以使机器人收集纸张。从技术上讲,你可以最大化 M 次,您可以执行以下操作之一:

  • 移动支柱:将任意一列移动到另一个单元格。但是,您无法选择存在机器人或柱子的单元格作为目的地。
  • 滚动机器人:向上、下、左、右任意方向滚动机器人。
    • 机器人会按照指定方向继续滚动,当碰到柱子所在的单元格时,会停在柱子正前方的单元格处。如果没有可以碰撞的柱子,它会在离开网格之前停在单元格处。
    • 之后,如果停止的单元格中有一张写有字符的纸,请让机器人收集它。但是,如果机器再次停在您已收集过纸张的单元格中,您将无法再次收集纸张。

完成所有操作后,按照机器人收集的顺序排列纸张,并获得“连续相同字母长度的平方和”的分数。
(例如,工作表 如果按照 A, B, B, B, A, B的顺序收集,得分为 \(1^2 + 3^2 + 1^2 + 1^2 = 12 \)。 )

通过移动机器人和柱子来最大化你的分数。

每个测试用例和该问题的分数计算如下:

  • 对于一个测试用例,操作完成后的分数即为分数。
  • 总共 50 个存在。各 tstoke-su 的得分总和,将作为本题的得分。

入力

输入是按以下格式从标准输入给出的。

N P M
row_{0}
\(\vdots\)
row_{N-1}
sheets_{0}
\(\vdots\)
sheets_{N-1}
  • N 是表示网格大小的整数,N = 40 满足
  • P 是表示列数的整数,P = 300 满足
  • M 是问题中指定的操作可以执行的最大次数,M = 1000 满足
  • row_{i} 是长度 N 字符串,其中每个字符是 第 o, x, -。row_{i} 可以得到第 j 个字符 (\( 0 \leq i,j \lt N \)) 是
    • o 如果 (i,j) 中有一个机器人
    • x 如果 (i,j) 中有一根柱子
    • - 如果 (i,j) 中没有机器人或柱子 代表
    。另外,row_0 减去 row_{N-1} , 选择最大化o是一个字符, 保证是x只是 P 角色。 第
  • sheets_{i} 是长度 N 字符串,其中每个字符是 第 A 减去 Z。 sheets_{i} 可以得到第 j 个字符 (\( 0 \leq i,j \lt N \)) 是 代表写在(i,j) 中的纸张上的字符。

出力

最大M 行。请按照从上到下的顺序输出要执行的操作。

  • 移动支柱如果位于行首 输出P以及该列所在的单元格(r_{1}, c_{1}) 和目标单元格 输出(r_{2}, c_{2})以空格分隔,如下 (\( 0 \leq r_1, c_1, r_2, c_2 \lt N \) )。操作前 如果 (r_{1}, c_{1})中没有列并且 如果(r_{2}, c_{2})中有机器人或柱子, 。 对于
    P r_1 c_1 r_2 c_2
    
  • 滚动机器人,代表轧制方向的字符为 请从 UDLR 中输出1(分别对应上、下、左、右)。
  • [UDLR]
    

关于 tstokesu 的生成

每个用例均由测试用例生成器生成。
测试用例生成器可从页面底部的链接获取。
机器人和柱子的初始放置以及纸上写的字符都是根据统一随机数生成的。有关详细信息,请参阅测试器实现。


入力例

4 2 6
----
-o--
x---
-x--
XYZX
ZAYX
ZBZB
XYZX
这种情况是说明性的,不满足任何输入约束。 从

出力例

D
R
L
P 2 0 0 1
U
我将解释输入/输出示例。
程序输出 説明 机器人和支柱位置 已放置的表 找到表
输入给出的初始状态。机器人第一 您将位于一张标有 (1,1)留在A的工作表上,但请注意,此时无法拾取此工作表。 继续从
----
-o--
x---
-x--
XYZX
ZAYX
ZBZB
XYZX
无
D
机器人是 (1,1) 向下移动, 我撞到了(3,1) 处的一根柱子, 它将停止在(2,1) 。放置在那里 让他们收集写有 B的表格。 继续从
----
----
xo--
-x--
XYZX
ZAYX
Z ZB
XYZX
B
R
机器人是 (2,1) 向右移动,直到位于网格边缘。 从 (2,3) 。放置在那里 让他们收集写有 B的表格。 继续从
----
----
x--o
-x--
XYZX
ZAYX
Z Z
XYZX
BB
L
机器人是 (2,3) 继续向左移动, 它将停止在(2,0) 处的一根柱子, 它将停止在(2,1) 。由于这里已经收过该表,因此无法再次收表。 柱子放置在
----
----
xo--
-x--
XYZX
ZAYX
Z Z
XYZX
BB
P 2 0 0 1
(2,0) 转至(0,1) 。 继续从
-x--
----
-o--
-x--
XYZX
ZAYX
Z Z
XYZX
BB
U
机器人是 (2,1) 向上移动 让他们收集写有(0,1) 处的一根柱子, 它将停止在(1,1) 。放置在那里 让他们收集写有 A的表格。您可以再执行一项操作,或中途停止。
-x--
-o--
----
-x--
XYZX
Z YX
Z Z
XYZX
BBA
在这种情况下,分数将为 \( 2^2 + 1^2 = 5 \) 分。

生成器和测试器以及样本输入数据

测试用例生成器、测试器和示例输入数据由以下链接提供。

发电机测试仪样本输入数据


展示台

我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。

  • 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。

展示台

输入文件
输出文件
fps
命令
最后
分数 本实验的
另存为图像