← 返回题目列表

AtCoder · future_contest_2019_qual_a

A. 分解机器人

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

配点 : 150000 点

問題文

有一个机器人可以读取一系列指令并在板上行走。在这个问题中,命令 是什么? S, L, R 的 3 字符类型,命令列 是由这些字符组成的字符串。

长度 L (= 300) 的指令序列是 给出了 N (= 500) 。你的任务是M \times M (M = 29) 构建一个方格板, 目的是使机器人停止在尽可能多的不同位置,以响应一系列N 指令。

机器人从棋盘的中心方格开始移动(从顶部 15 正方形,从左起 15 向上看开始运算,从左开始按顺序执行指令串中包含的指令。各命令的效果如下。

  • S : 在你当前面对的方向 1 前进。
  • L : 90 向左旋转。
  • R : 90 向右旋转。

但是,您可以用影响这些订单效果的方块来构建您的棋盘。可以使用的方块如下。

  • . :普通正方形。在这个方块上执行的命令将达到预期的效果。
  • # :这是一个墙壁空间。当机器人尝试进入这个方格时,移动将会失败,并且机器人不会从之前的方格移动。此外,棋盘上所有最外面的方格都必须是墙方格。
  • D : 2 双正方形。在这个方块上执行命令的效果是 它连续被激活 2 次(忽略穿过的方块的影响)。
  • T : 3 双正方形。在这个方块上执行命令的效果是 它连续被激活 3 次(忽略穿过的方块的影响)。
  • L : L这是一条鳟鱼。在这个广场上指挥 当执行 R 时,在普通方块上 其效果与执行 L 时的效果相同。
  • R : R这是一条鳟鱼。在这个广场上指挥 当执行 L 时,在普通方块上 其效果与执行 R 时的效果相同。

您可以使用任意数量的每个方块。

重申你的任务: 目标是构建一个板,允许机器人响应一系列N 指令而停止在尽可能多的不同位置。 更具体地说,您构建的董事会将获得如下积分: 每个方格的

  • 每个正方形的 停止计数 在 0 。
  • 对于每个命令序列,让机器人从中心方格执行命令序列,并计算执行结束时机器人所站立的方格的停止计数。 1 增加。
  • 每个方格的点数确定如下。
    • 停止计数为 1 ,该方格的得分为 10 点。
    • 停止计数为 2 ,该方格的得分为 3 点。
    • 停止计数为 3 ,该方格的得分为 1 点。
    • 除上述情况外,该方格的得分为 0 点。
  • 所有方格的分数之和就是该棋盘的分数。

搭建棋盘以获得尽可能高分。

制約

  • N = 500
  • M = 29
  • L = 300
  • S_i 是长度 它是一个 L 字符串。 字符
  • S_i 是 1 每个字母都是独立选择的,50概率为 % S、25概率为 % L、25概率为 % R 变为。 给定了

入力

输入按以下格式给出。

N M L
S_1
S_2
:
S_N

出力

按以下格式输出最高分的棋盘。

T_1
T_2
:
T_M

这里 T_i 是每个长度 是一个字符串 M , 不得包含除., #, D, T, L, R 之外的任何字符。

另外,棋盘上最外面的字符(即T_1, T_M 中的所有字符以及每个 T_i 的第一个和最后一个字符都是 # 必须是T_{15} 的 15 第一个字符是 不得为 # 。

採点

单个测试用例的分数是使用问题文本中描述的方法计算的。

测试用例是 30 给定一个案例,所有测试用例的分数总和就是该提交的分数。

在 example_01 以外的情况下, 1 如果即使在这种情况下输出也无效,则除 example_01 之外的所有情况的分数都将是 0 点。

入力例0

6 7 7
RSLSSRS
RSSLSSS
SRSLLLL
RSLSLLL
LSLSLLL
RRSRSRR

出于说明目的,此输入尺寸较小,并且不满足约束条件。

出力例0

#######
#....##
#..L..#
#.T...#
#..D..#
#R....#
#######

对于每个命令序列,机器人停止的方格如下, 您可以获得60 积分。

#######
#.5.1##
#.3642#
#.....#
#.....#
#.....#
#######

入力例1

单击此处获取输入文件和输出示例 (zip)

分级结果“example_01”是该数据。该数据也将被评分。