← 返回题目列表

AtCoder · rcl_contest_2020_qual_b

B. 插画家X和神秘的笔

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

問題文

irasutore画师用神奇的笔画画。这支笔出的颜色会每秒按顺序依次变化:红色 → 黄色 → 绿色 → 黄色。

下图是 X 接下来打算画的图的计划示例。 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
命令
分数 本实验的
另存为图像