問題文
irasutore画师用神奇的笔画画。这支笔出的颜色会每秒按顺序依次变化:红色 → 黄色 → 绿色 → 黄色。
下图是 X 接下来打算画的图的计划示例。
X 按以下步骤画画。
- (1)将画纸N 行 N 分成列的网格。从上往下 i 第几行,从左边开始 j 列单元格 表示为 (i, j) 表示。对于每个单元格,计划用哪种颜色的笔涂色。
- (2)给四个角的单元格上色。(0, 0) 涂成红色,(0, N-1) 涂成蓝色,(N-1, 0) 涂成绿色,(N-1, N-1) 涂成黄色。其他的单元格没有涂颜色。
- (3)M 在每秒之间,每1秒选择以下任意一项进行执行。首次使用画笔时可以用红色涂。
- 涂线:使用画笔进行上色。选择与即将涂的颜色相同的单元格,从那里沿上下左右的任意方向 5 涂上颜色。
- 例如,(r,c)如果从...向上涂,(r-1,c) 减去 (r-5,c) 。
- 但是,从网格突出的部分将不会被绘制。
- 如果您尝试填充的单元格已经着色,则旧颜色将被擦除并被您尝试填充的颜色覆盖。
- 不执行任何操作:等待下一个颜色改变。
X已完成绘制过程的步骤(1)和(2),并且即将开始步骤(3)。一旦您决定了计划为每个单元绘制哪种颜色,请通过良好的绘制来最大化根据 X 计划着色的单元数量。
每个测试用例和该问题的分数计算如下:
- 在一个测试用例中,分数是根据 X 中的计划着色的单元格数量。
- 总共有 50 个。各测试用例的分数总和,就是这个问题的分数。
入力
输入是按以下格式从标准输入给出的。
\(\begin{array}{lll}
N ~ M & & \\
A_{ 0,0 } & \ldots & A_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
A_{ N-1,0 } & \ldots & A_{ N-1,N-1 }
\end{array}\)
- N 是一个整数,代表您绘制图片的纸张尺寸,N = 50 满足…
- M 是X执行步骤(3)中指定的操作的次数,M = 500 满足…
- A_{i,j} 是 您也可以写 i 行 j 在该列中,X代表您要绘制的颜色, 0 ≤ A_{i,j} ≤ 3 满足… A_{i,j} 是 在 0 变为红色, 1 然后是蓝色, 2 然后绿色, 3 表示您要将其涂成黄色。 请输出
- A_{0,0} = 0 , A_{0,N-1} = 1 , A_{N-1,0} = 2 , A_{N-1,N-1} = 3 满足…
出力
M 行。请按照从上到下的顺序输出要执行的操作。
- 涂线如果所选单元格的位置 (r,c) ( 0 ≤ r,c ≤ N-1 )和指示绘画方向的字符。
请输出
UDLR(对应上、下、左、右)中的一个,以空格分隔。如果所选单元格的颜色与您要填充的颜色不匹配, 请输出 。 对于 - 不执行任何操作場合、
-1。
关于测试用例的生成
每个用例均由测试用例生成器生成。
测试用例生成器可从页面底部的链接获取。
作为 X 绘画计划示例的图像是
这是 seed = 1, 2, 3 的示例。
测试用例生成器使用以下步骤生成用例。有关详细信息,请参阅测试器实现。没有必要把解释和实现都通读一遍。
- 首先,初始化网格单元和生成过程中使用的列表,如下所示。
- 最初,所有单元格都是未着色的。
- 给四个角上色。 将 (0, 0) 涂成红色,(0, N-1) 涂成蓝色,(N-1, 0) 涂成绿色,(N-1, N-1) 涂成黄色。
- 对于每种颜色,随机选择未着色的单元格。 3 减去 10 选择一个正方形并为其着色。
- 每个彩色单元格 选取 (i, j) 并选择上方、下方、左侧和右侧的单元格。 将 (i, j) 颜色和单元格坐标对添加到列表中。
- 接下来,重复以下步骤,用颜色填充网格,直到列表为空。
- 从列表中随机选择一对,如果该对的单元格已填满则跳过。否则,在使用配对颜色填充单元格后,按照与之前相同的方式将填充颜色和四个相邻单元格添加到列表中。
- 最后检查网格是否满足以下条件:如果不满足条件,则从头开始重新生成该案例。
- 输出满足的条件:每种颜色的单元格数量至少为 \( \lfloor N ^ 2 / 6 \rfloor \)。
入力例
7 8 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 2 2 2 2 2 1 1 2 2 2 2 3 1 1 2 2 2 3 3 3 3 2 2 3 3 3 3 3这种情况是说明性的,不满足任何输入约束。 从
出力例
0 0 R 0 6 L 6 0 R 6 6 D -1 0 2 D 6 3 R -1
- (0, 0) 开始, 从 (0, 1) 向右 将 (0, 5) 涂成红色。 从
- (0, 6) 开始, 从 (0, 5) 向左 将 (0, 1) 涂成蓝色。已经涂成红色的区域也将被覆盖。 将
- (6, 0) 开始, 从 (6, 1) 向右 将 (6, 5) 涂成绿色。 我试图从
- (6, 6) 开始用黄色绘制底部,但由于它从网格中突出,所以我无法在任何地方绘制。
- 现在轮到你把它涂成红色了,但你也可以什么都不做。
- (0, 2) 开始, 从 (1, 2) 下来 (5, 2) 涂成蓝色。 将
- (6, 3) 开始, 从 (6, 4) 向右 将 (6, 6) 涂成绿色。从网格突出的区域将不会被绘制。
- 由于没有单元格被涂成黄色,所以你不能在任何地方涂上黄色,也不能做任何事情。
- 由于按计划绘制了 7 个单元格,因此您将获得 7 分。
生成器和测试器以及样本输入数据
测试用例生成器、测试器和示例输入数据由以下链接提供。
展示台
我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。
- 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。
- 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
- 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。
还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。
输入文件
输出文件
fps
命令
分数
本实验的